POJ2387 Til the Cows Come Home 【Dijkstra】

题目链接:http://poj.org/problem?id=2387

题目大意;

题意:给出两个整数T,N,然后输入一些点直接的距离,求N和1之间的最短距离。。

思路:dijkstra求单源最短路,但是要注意判重。
 
#include <cstdio>
#include <cstring>
#define inf 0x3f3f3f3f
#define min(a,b) a<=b?a:b
int vis[], dis[]; //dis[j]表示起点到当前点的最短距离
int n, t;
int map[][]; void dij()
{
int i, j, cur, k;
memset(vis, , sizeof(vis));
for (i = ; i <= n; i++)(i == ) ? (dis[i] = ) : (dis[i] = inf);
cur = ;
for (i = ; i < n; i++) //循环n次,每次挑选没走过的到起点距离最短的点
{
vis[cur] = ;
for (j = ; j <= n; j++)
{
if (vis[j] == )
dis[j] = min(dis[j], map[cur][j] + dis[cur]); //更新每个没走过的点,到起点的最短距离
} //选择到起点距离最短的点
int g = inf; int x = ;
for (j = ; j <= n; j++)
{
if (dis[j] <= g && !vis[j])
{
g = dis[j];
x = j;
}
}
cur = x;
}
printf("%d\n", dis[n]); //输出终点到起点的最短距离
} int main()
{
int i, j, a, b, c;
while (scanf("%d%d", &t, &n) != EOF)
{
memset(map, inf, sizeof(map));
for (i = ; i <= t; i++)
{
scanf("%d%d%d", &a, &b, &c); //去除重边的情况
if (c < map[a][b])
map[a][b] = map[b][a] = c;
}
dij();
}
return ;
}

2018-04-01

上一篇:const类型变量的详细解读


下一篇:iOS 图片加载导致内存警告