hdu1874畅通工程续

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

floyd: 62MS

View Code

 1 #include<iostream>
 2 using namespace std ;
 3 #define maxn 210
 4 const int oo = 1<<28 ;
 5 int map[maxn][maxn] ;
 6 int n ;
 7 void init()
 8 {
 9     for(int i=0; i<n; i++)
10     for(int j=0; j<n; j++)
11     {
12         map[i][j] = oo ;
13         if(i==j)
14         map[i][j] = 0 ;
15     }
16 }
17 void floyd()
18 {
19     for(int k=0; k<n; k++)
20     for(int i=0; i<n; i++)
21     for(int j=0; j<n; j++)
22     if(map[i][j]>map[i][k]+ map[k][j])
23     map[i][j] = map[i][k] + map[k][j] ;
24 }
25 int main()
26 {
27     int m, a, b, c, s, t ;
28     while(cin>>n>>m)
29     {
30         init() ;
31         while(m--)
32         {
33             cin>>a>>b>>c ;
34             if(map[a][b]>c)
35             map[a][b] = map[b][a] = c ;
36         }
37         cin>>s>>t ;
38         floyd() ;
39         if(map[s][t]<oo)
40         cout<<map[s][t]<<endl ;
41         else
42         cout<<"-1"<<endl ;
43     }
44     return 0 ;
45 }

dijkstra: 15MS

View Code

 1 #include<iostream>
 2 #include<map>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<string>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 #define MAX 0x3f3f3f3f
10 #define N 210
11 int num, road, dis[N], len[N][N];
12 bool visit[N];
13 
14 
15 void Dijkstra(int start)
16 {
17     int k, temp;
18     memset(visit, 0, sizeof(visit));
19     for(int i = 0; i < num; ++i) //初始化
20         dis[i] = (i==start ? 0 : MAX);
21     for(int i = 0; i < num; ++i)
22     {
23         temp = MAX;
24         for(int j = 0; j < num; ++j) //查找最短路
25             if(!visit[j] && dis[j] < temp)
26                 temp = dis[k = j];
27         visit[k] = 1;
28         for(int j = 0; j < num; ++j) //更新源点到其他点的最短路
29             if(!visit[j] && dis[j] > dis[k] + len[k][j])
30                 dis[j] = dis[k] + len[k][j];
31     }
32 }
33 
34 int main()
35 {
36     int a, b, cost, start, end;
37     while(scanf("%d%d", &num, &road) != EOF)
38     {
39         memset(len, MAX, sizeof(len));
40         for(int i = 0; i < road; ++i)
41         {
42             scanf("%d%d%d", &a, &b, &cost);
43             if(cost < len[a][b]) //一条路可以有多个cost，记录最小的。注意~~~
44             len[a][b] = len[b][a] = cost;
45         }
46         scanf("%d%d", &start, &end);
47         Dijkstra(start);
48         if(dis[end] == MAX) printf("-1\n");
49         else printf("%d\n", dis[end]);
50     }
51     return 0;
52 }