hdu 1874 畅通工程续(模板题 spfa floyd)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1874

spfa 模板

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<queue>
 5 using namespace std;
 6 
 7 const int INF=1<<28;
 8 int cnt,head[1100],d[210],vis[210],n,m;
 9 queue<int>q;
10 
11 struct node
12 {
13     int u,v,w,next;
14 } edge[1100];
15 
16 void add(int u,int v,int w)
17 {
18     edge[cnt].u=u;
19     edge[cnt].v=v;
20     edge[cnt].w=w;
21     edge[cnt].next=head[u];
22     head[u]=cnt++;
23 };
24 
25 void spfa(int s)
26 {
27     int i,u,v;
28     for(i=0; i<n; i++)
29         d[i]=INF;
30     d[s]=0;
31 
32     q.push(s);
33     vis[s]=1;
34     while(!q.empty())
35     {
36         u=q.front();
37         q.pop();
38         vis[u]=0;
39         for(i=head[u]; i!=-1; i=edge[i].next)
40         {
41             v=edge[i].v;
42             if(d[u]+edge[i].w<d[v])
43             {
44                 d[v]=d[u]+edge[i].w;
45                 if(!vis[v])
46                 {
47                     vis[v]=1;
48                     q.push(v);
49                 }
50             }
51         }
52     }
53 };
54 int main()
55 {
56     int u,v,w,s,t;
57     while(cin>>n>>m)
58     {
59         cnt=0;
60         memset(head,-1,sizeof(head));
61         memset(vis,0,sizeof(vis));
62         while(m--)
63         {
64             cin>>u>>v>>w;
65             add(u,v,w);
66             add(v,u,w);
67         }
68         cin>>s>>t;
69         spfa(s);
70         if(d[t]<INF) cout<<d[t]<<endl;
71         else cout<<-1<<endl;
72     }
73 }

floyd 模板

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int oo = 1<<28;
 4 int map[201][201];
 5 
 6 int n, m;
 7 void floyd()
 8 {
 9     int k,i,j;
10     for( k = 0; k < n; k++)
11         for( i = 0; i < n; i++)
12             for( j = 0; j < n; j++)
13                 if(map[i][k]+map[k][j] < map[i][j])
14                     map[i][j] = map[i][k]+map[k][j];
15 }
16 void init()
17 {
18     int i,j;
19     for( i = 0; i < n; i++)
20     {
21         for(j = 0; j < n; j++)
22             map[i][j] = oo;
23         map[i][i] = 0;
24     }
25 }
26 int main()
27 {
28     int i;
29     while(~scanf("%d %d", &n, &m))
30     {
31         init();
32         int u, v, w;
33         for( i = 0; i < m; i++)
34         {
35             scanf("%d %d %d", &u, &v, &w);
36             if(map[u][v] > w)
37             {
38                 map[u][v] = w;
39                 map[v][u] = w;
40             }
41         }
42         floyd();
43         scanf("%d %d", &u, &v);
44         if(map[u][v] < oo)
45             printf("%d
", map[u][v]);
46         else
47             printf("-1
");
48     }
49     return 0;
50 }