我的第一个最短路的题目。
坑的是，题目说路径C最大是1000.我就把最大值INF设成了10000；
结果WA了，好几次，找不出错。。最后改了INF=0x3f3f3f3f才A的。。。哎。。数据怎么搞得，切！！！
#include <iostream>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXV=105;
int cost[MAXV][MAXV];
void Dijkstra(int n)
{
int dist[MAXV];
bool s[MAXV];
for(int i=1;i<=n;i++)
{
dist[i]=cost[1][i];
s[i]=0;
}
s[1]=1;
int k;
for(int i=1;i<=n;i++)
{
int min=INF;
for(int j=1;j<=n;j++)
{
if(s[j]==0&&dist[j]<min)
{
k=j;
min=dist[j];
}
}
s[k]=1;
for(int j=1;j<=n;j++)
{
if(s[j]==0)
if(cost[k][j]<INF&&dist[k]+cost[k][j]<dist[j])
dist[j]=dist[k]+cost[k][j];
}
}
printf("%d
",dist[n]);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
break;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cost[i][j]=INF;
}
}
int a,b,c;
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
cost[a][b]=cost[b][a]=c;
}
Dijkstra(n);
}
return 0;
}