poj2387 Til the Cows Come Home（Dijkstra）

题目链接

http://poj.org/problem?id=2387

题意

有n个路标，编号1~n，输入路标编号及路标之间相隔的距离，求从路标n到路标1的最短路径（由于是无向图，所以也就是求从路标1到路标n的最短路径）。

思路

最短路径问题，由于结点数目最多可以有1000个，用Floyd算法应该会超时，而且做了之后发现输入会有相同的边，使用SPFA算法会麻烦一些，所以这里使用Dijkstra算法求解。

代码

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int INF = 0x3f3f3f;

 const int N =  + ;

 int map[N][N];

 int dist[N];

 int visit[N];

 int n, t;

 void dijkstra()

 {

     for (int i = ; i <= n; i++)

         dist[i] = map[][i];

     dist[] = ;

     int min_dist, now = ;

     for (int i = ; i <= n; i++)

     {

         visit[now] = ;

         min_dist = INF;

         for (int j = ; j <= n; j++)

         {

             if (!visit[j] && dist[j] < min_dist)

             {

                 min_dist = dist[j];

                 now = j;

             }

         }

         visit[now] = ;

         for (int j = ; j <= n; j++)

             dist[j] = min(dist[j], dist[now] + map[now][j]);

     }

     printf("%d\n", dist[n]);

 }

 int main()

 {

     //freopen("poj2387.txt", "r", stdin);

     scanf("%d%d", &t, &n);

     memset(map, INF, sizeof(map));

     int a, b, d;

     for (int i = ; i < t; i++)

     {

         scanf("%d%d%d", &a, &b, &d);

         if(map[a][b] > d)    //对于相同的边，取权值最小的那条

             map[a][b] = map[b][a] = d;

     }

     dijkstra();

     return ;

 }