POJ2387 Til the Cows Come Home(最短路径)

题意：

输入一个图，给出每条边的权值，以1为起点，要求到n的最短路径。

要点：

今天学了一下最短路，有好多种算法，估计要做好长一段时间了。这题就是最简单的模板，就是稍微注意一下可能有重边。这题用的dijkstra算法，主要是贪心，证明还不会。以后看看能不能推一下。

参考博客：点击打开链接  点击打开链接

dijkstra算法：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 1010
#define INF 0x3f3f3f3f
int map[maxn][maxn];
int dis[maxn];		//起点到j的最短路径
bool vis[maxn];		
int n, m;void dijkstra()
{int i, j, temp,min;memset(vis, true, sizeof(vis));for (i = 1; i <= n; i++){vis[1] = false;dis[i] = map[1][i];}for (i = 1; i <= n; i++){min = INF;for (j = 1; j <= n; j++)if (vis[j] && min > dis[j])//选出当前点发散的最小边{min = dis[j];temp = j;	}vis[temp] = false;			//将运算过的点剔除for (j = 1; j <= n; j++){if (vis[j] && dis[j] > map[temp][j] + dis[temp])//这里进行更新，保证dis储存最短路径dis[j] = map[temp][j] + dis[temp];}}}int main()
{int a,b,c;while (~scanf("%d%d", &m, &n)){memset(map, INF, sizeof(map));while (m--){scanf("%d%d%d", &a, &b, &c);if(c<map[a][b])				//如果有重边选最小的那条map[a][b] = map[b][a] = c;}dijkstra();printf("%d\n", dis[n]);}return 0;
}