POJ 0332 The Flash
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了POJ 0332 The Flash，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4483字，纯文字阅读大概需要7分钟。
内容图文
传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=302
| The Flash |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
"My name is Barry Allen and I‘m the fastest man alive. When I was a child, I saw my mom killed by something impossible, and my father went to prison for her murder. Then an accident made me the impossible. To the outside world, I‘m an ordinary forensic scientist. But secretly, I used my speed to fight crim and find others like me. And one day, I‘ll find who killed my mother and get justice for my father. I am the flash." 以上是xjr背诵的闪电侠片头的片段。
B.I.T.C.H.们玩得正High时，闪电侠来得瑟他的速度了。他邀请xjr和Avengers观看他夜晚在城市跑步的场景。 他的路线是这样的：（一共有n个城市，城市由1到n编号，城市之间有m条边） 1 → 2 → 1 → 3 → 1 → 4 → 1 → 5 → 1 → … → n-1 → 1 → n → 1 但由于闪电侠速度超过闪电，他也有了一种和电流一样的心理——走最短路，现在你需要回答闪电侠最少需要走多少千米的路程。 |
|
输入
|
|
第一行，两个整数n和m（见试题描述）
接下来m行，每行三个整数a，b和c，表示从a城市到b城市有一条有向边，长度为c |
|
输出
|
|
闪电侠走的最短路程
|
|
输入示例
|
|
5 10
2 3 8 1 5 90 3 5 82 1 2 76 1 3 8 5 3 4 4 1 23 4 5 6 3 5 6 5 4 2 |
|
输出示例
|
|
232
|
|
其他说明
|
|
1 < n, c < 1001
1 < m < 100001 数据保证城市1能到达任何城市，并且任何城市能到达城市1 |
题解：最短路瞎跑大水题（出题人竟然没有卡SPFA！！！）
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #include<queue>
6 #include<cstring>
7#define inf 10000000
8#define PAU putchar(‘ ‘)
9#define ENT putchar(‘\n‘)
10usingnamespace std;
11constint maxn=1000+10,maxm=100000+10;
12struct ShortiestPath{
13struct Tedge{int x,y,w,next;}adj[maxm];int fch[maxn],ms;
14int d[maxn],S,n;bool inque[maxn];
15void AddEdge(int u,int v,int w){adj[++ms]=(Tedge){u,v,w,fch[u]};fch[u]=ms;return;}
16void init(int S,int n){
17this->S=S;this->n=n;ms=0;
18 memset(inque,false,sizeof(inque));
19 memset(fch,0,sizeof(fch));
20for(int i=1;i<=n;i++) d[i]=inf;
21return;
22 }
23void SPFA(){
24 queue<int>Q;d[S]=0;Q.push(S);
25while(!Q.empty()){
26int u=Q.front();Q.pop();inque[u]=false;
27for(int i=fch[u];i;i=adj[i].next){
28int v=adj[i].y;
29if(d[v]>d[u]+adj[i].w){
30 d[v]=d[u]+adj[i].w;
31if(!inque[v]){
32 inque[v]=true;
33 Q.push(v);
34 }
35 }
36 }
37 } return;
38 }
39}p1,p2;
40 inline int read(){
41int x=0,sig=1;char ch=getchar();
42while(!isdigit(ch)){if(ch==‘-‘)sig=-1;ch=getchar();}
43while(isdigit(ch))x=10*x+ch-‘0‘,ch=getchar();
44return x*=sig;
45}
46 inline void write(int x){
47if(x==0){putchar(‘0‘);return;}if(x<0)putchar(‘-‘),x=-x;
48int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
49for(int i=len-1;i>=0;i--)putchar(buf[i]+‘0‘);return;
50}
51int n,m;
52void init(){
53 n=read();m=read();
54 p1.init(1,n);p2.init(1,n);
55for(int i=1;i<=m;i++){
56int a=read(),b=read(),c=read();
57 p1.AddEdge(a,b,c);
58 p2.AddEdge(b,a,c);
59 }
60return;
61}
62void work(){
63 p1.SPFA();p2.SPFA();
64return;
65}
66void print(){
67int ans=0;
68for(int i=1;i<=n;i++){
69 ans+=p1.d[i]+p2.d[i];
70 }
71 write(ans);
72return;
73}
74int main(){init();work();print();return0;}
当然啦还是写Dijkstra比较稳妥，小健建のDijkstra：（原谅我懒到一定境界了。。。）
1 #include<cstdio>
2 #include<cstring>
3 #include<queue>
4 #include<algorithm>
5usingnamespace std;
6constint maxn=1010;
7constint maxm=100010;
8constint INF=100000000;
9struct Edge
10{
11intfrom,to,dist;
12};
13struct Heapnode
14{
15int d,u;
16booloperator < (const Heapnode& rhs) const17 {
18return d>rhs.d;
19 }
20};
21struct Dijkstra
22{
23int n,m;
24int p[maxn];
25 Edge edges[maxm];
26int first[maxn],next[maxm];
27int d[maxn];
28bool done[maxn];
29void init(int n)
30 {
31this->n=n;
32 m=0;
33 memset(first,0,sizeof(first));
34 }
35void AddEdge(intfrom,int to,int dist)
36 {
37 edges[++m]=(Edge){from,to,dist};
38 next[m]=first[from];
39 first[from]=m;
40 }
41void dijkstra(int s)
42 {
43 memset(done,0,sizeof(done));
44 priority_queue<Heapnode> Q;
45for(int i=1;i<=n;i++) d[i]=INF;
46 d[s]=0;
47 Q.push((Heapnode){0,s});
48while(!Q.empty())
49 {
50 Heapnode x=Q.top();
51 Q.pop();
52if(done[x.u]) continue;
53 done[x.u]=1;
54for(int i=first[x.u];i;i=next[i])
55 {
56 Edge& v=edges[i];
57if(d[v.to]>d[x.u]+v.dist)
58 {
59 d[v.to]=d[x.u]+v.dist;
60 Q.push((Heapnode){d[v.to],v.to});
61 }
62 }
63 }
64 }
65}sol1,sol2;
66int main()
67{
68int n,m,a,b,c;
69 scanf("%d%d",&n,&m);
70 sol1.init(n); sol2.init(n);
71while(m--)
72 {
73 scanf("%d%d%d",&a,&b,&c);
74 sol1.AddEdge(a,b,c);
75 sol2.AddEdge(b,a,c);
76 }
77 sol1.dijkstra(1); sol2.dijkstra(1);
78longlong ans=0;
79for(int i=1;i<=n;i++) ans+=sol1.d[i]+sol2.d[i];
80 printf("%lld\n",ans);
81return0;
82 }
原文：http://www.cnblogs.com/chxer/p/4474014.html
内容总结
以上是互联网集市为您收集整理的POJ 0332 The Flash全部内容，希望文章能够帮你解决POJ 0332 The Flash所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。