题目链接

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 ;
}
05-11 11:24