/*
对于只会弗洛伊德的我，迪杰斯特拉有点不是很理解，后来发现这主要用于单源最短路，稍稍明白了点，不过还是很菜，这里只是用了邻接矩阵
套模板，对于邻接表暂时还，，，没做题，后续再更新。现将这题贴上，应该是迪杰斯特拉最水的题没有之一。纯模板
找到距离起点最近的点，以此点为中间点进行更新，找到了在进行下一个点。
*/
题目大意：
搬东西很累，想省力，给你几个点和点之间的距离；标准题型；
#include<stdio.h>
#include <iostream>
#include<string.h>
using namespace std;
#define inf 0xfffffff
int map[][],dis[],visit[];
int n,m; int dijstra()
{
memset(visit,,sizeof(visit));
for (int i=;i<=n;i++)
{
dis[i]=map[][i];
}
visit[]=;
dis[]=;
for (int i=;i<=n;i++)
{
int pos;
int min=inf;
for (int j=;j<=n;j++)
{
if (!visit[j]&&min>dis[j])
{
pos=j;
min=dis[j];
}
}
visit[pos]=;
for (int j=;j<=n;j++)
{
if (!visit[j]&&dis[j]>dis[pos]+map[pos][j])
{
dis[j]=dis[pos]+map[pos][j];
}
}
}
return dis[n];
}
int main ()
{
int i,j;
while(~scanf("%d%d",&n,&m),n||m)
{
for(i=;i<=n;++i)
{
for(j=;j<=n;++j)
{
map[i][j]=inf;
}
}
int a,b,c;
for(i=;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&c);
if(c<map[a][b])
map[a][b]=map[b][a]=c;
}
// for (int i=1;i<=n;i++)
// {
// for (int j=1;j<=n;j++)
// {
// cout<<map[i][j]<<" ";
// }cout<<endl;
// }
int count=dijstra();
printf("%d\n",count);
}
return ;
}
PS：后续更新邻接表的题型。。