标准的dijkstra啊,模板啊模板。
Dijkstra算法原理详细讲解
如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）
算法执行步骤如下表：
上面好像已经说的很清楚了。
#include<iostream>
using namespace std;
int Max=1000001;
intmain(void)
{
int map[105][105],end,n,i,j,flag[105],min,value;
int a,b,ans[105],d;
while(scanf("%d%d",&end,&n),end||n)
{
memset(flag,0,sizeof(flag));
for(i=0;i<=end;i++)
for(j=0;j<=end;j++) map[i][j]=Max;
for(i=0;i<n;i++)
{
scanf("%d%d%d",&a,&b,&value);
map[a][b]=map[b][a]=value;
}
for(i=1;i<=end;i++)
ans[i]=map[1][i];
flag[1]=1;
for(i=1;i<end;i++)
{
min=Max;
for(j=1;j<=end;j++)
{
if(flag[j]==0&&ans[j]<min)
{
min=ans[j];
d=j;
}
}
flag[d]=1;
for(j=1;j<=end;j++)
{
if(flag[j]==0&&(map[d][j
]+ans[d])<ans[j])
{
ans[j]=map[d][j]+ans[d];
}
}
}
printf("%d\n",ans[end]);
}
return0;
}