首页 > 代码库 > hdu 2680 Choose the best route 解题报告

hdu 2680 Choose the best route 解题报告

2024-07-05 17:36:52   226人阅读

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

题目意思：实质就是给定一个多源点到单一终点的最短路。

     卑鄙题～～～有向图。初始化map时 千万不要写成 map[i][j] = map[j][i] = X。

    

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 #define INF 0xfffffff
 8 const int maxn = 1000 + 5;
 9 int dist[maxn], map[maxn][maxn], vis[maxn];
10 int n, m, s;
11 
12 void Init()
13 {
14     for (int i = 0; i <= n; i++)
15     {
16         for (int j = 0; j <= n; j++)
17             map[i][j] = (i == j ? 0 : INF);
18     }
19     int p, q, t, w;
20     for (int i = 0; i < m; i++)
21     {
22         scanf("%d%d%d", &p, &q, &t);
23         if (map[p][q] > t)
24             map[p][q] = t;   // 写成map[p][q] = map[q][p] = t 会wa的！！！
25     }
26     scanf("%d", &w);
27     for (int i = 0; i < w; i++)
28     {
29         scanf("%d", &p);
30         map[0][p] = map[p][0] = 0;
31     }
32     for (int i = 0; i <= n; i++)
33         dist[i] = map[0][i];
34 }
35 
36 void Dijkstra()
37 {
38     int u, maxx;
39     memset(vis, 0, sizeof(vis));
40     for (int i = 0; i <= n; i++)
41     {
42         maxx = INF;
43         for (int j = 0; j <= n; j++)
44         {
45             if (!vis[j] && dist[j] < maxx)
46                 maxx = dist[u=j];
47         }
48         vis[u] = 1;
49         for (int j = 0; j <= n; j++)
50         {
51             if (dist[j] > dist[u] + map[u][j])
52                 dist[j] = dist[u] + map[u][j];
53         }
54     }
55 }
56 
57 int main()
58 {
59     while (scanf("%d%d%d", &n, &m, &s) != EOF)
60     {
61         Init();
62         Dijkstra();
63         printf("%d\n", dist[s] == INF ? -1 : dist[s]);
64     }
65     return 0;
66 }

 


联系
我们