2387 poj Til the Cows Come Home【dijkstra，经典&&基础】

野性酷女 2022-08-09 13:57 120阅读 0赞



Til the Cows Come Home














Time Limit: 1000MS

   Memory Limit: 65536K
Total Submissions: 37068   Accepted: 12622

Sample Input

  1. 5 5
  2. 1 2 20
  3. 2 3 30
  4. 3 4 20
  5. 4 5 20
  6. 1 5 100

Sample Output

  1. 90

题目大意：

给两个数 T , M 。T表示在接下来有T条边【即T行数据】，N表示有N个点，然后输入数据【注意1，重边时，取更短的】【注意2，数组开大点，笔者应为只开到100+，re了3次】，然后输出点 1 到点 N 的最小距离。

  1. #include <cstdio>
  2. #include <cstring>
  3. #define INF 1000000
  4. using namespace std;
  6. int t, n;
  7. int dis[1001], vis[1001];
  8. int map[1001][1001];            //数组开到1001就够了，之前笔者只开到 101 ，所以就re了3次 
  10. void Dijsktra() {
  11.     for(int i = 1; i <= n; i++) {
  12.         vis[i] = 0;
  13.         dis[i] = INF;
  14.     }
  15.     dis[1] = 0;
  16.     while(1) {
  17.         int v = -1;
  18.         for(int i = 1; i <= n; i++)
  19.             if(!vis[i] && (v == -1 || dis[v] > dis[i]))
  20.                 v = i;
  21.         if(v == -1)                //注意这句，没了就成死循环了 
  22.             break;
  23.         vis[v] = 1;
  24.         for(int i = 1; i <= n; i++)
  25.             if(dis[i] > dis[v] + map[v][i])
  26.                 dis[i] = dis[v] + map[v][i];
  27.     }
  28.     printf("%d\n", dis[n]);
  29. }
  31. int main() {
  32.     int a, b, c;
  33.     while(~scanf("%d %d", &t, &n)) {            //注意T为边数，N为点数 
  34.         for(int i = 1; i <= n; i++)
  35.             for(int j = 1; j <= n; j++)
  36.                 map[i][j] = (i == j ? 0 : INF);
  37.         for(int i = 0; i < t; i++) {
  38.             scanf("%d %d %d", &a, &b, &c);
  39.             if(map[a][b] > c)                    //重边取短的 
  40.                 map[a][b] = map[b][a] = c;
  41.         }
  42.         Dijsktra();
  43.     }
  44.     return 0;
  45. }

发表评论

表情：
评论列表 （有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读