题意：

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

要点：

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

参考博客：  

dijkstra算法：

15365926

Accepted

4164K

63MS

852B

2016-04-07 22:20:16

#include
    
     #include
     
      #include
      
       #define maxn 1010#define INF 0x3f3f3f3fint 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