题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544
这题的思路可以见这里（同一类型）：http://blog.csdn.net/xiaozhuaixifu/article/details/9232921
#include<iostream>
using namespace std;
const int maxn=101;
const int intmax=99999;
int weight[maxn][maxn]; //保存权值的邻接矩阵
int dis[maxn];
int s,t;
void dijkstra()
{
bool Sset[maxn];
memset(Sset,0,sizeof(Sset));
Sset[s]=1;
for(int i=0;i<maxn;i++)
{
int u,v;
int tmp=intmax;
for(int i=0;i<maxn;i++)
{
if(!Sset[i]&&dis[i]<tmp)
{
u=i;
tmp=dis[i];
}
}
Sset[u]=1;
for(int i=0;i<maxn;i++)
{
if(!Sset[i]&&weight[u][i]<intmax)
{
int newdis=dis[u]+weight[u][i];
if(newdis<dis[i])dis[i]=newdis;
}
}
}
}
int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0)break;
int a,b,x;
for(int i=1;i<maxn;i++)
for(int j=1;j<maxn;j++)
weight[i][j]=intmax;
for(int i=0;i<m;i++)
{
cin>>a>>b>>x;
if(x<weight[a][b]) //处理重边
weight[a][b]=weight[b][a]=x;
}
// cin>>s>>t;
for(int i=0;i<maxn;i++)dis[i]=weight[1][i];
dis[1]=0; //如果是起点到起点，则应该是0
dijkstra();
if(dis[n]<intmax)
cout<<dis[n]<<endl;
else cout<<-1<<endl; //不存的情况应该是：权值无穷大
}
return 0;
}