Problem Description 某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input 本题目包含多组数据，请处理到文件结束。 每组数据第一行包含两个正整数N和M(0
题解：
注意重边一个路径可能出现多次。判断一下。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN =
1010;
const int INF =
0x3f3f3f3f;
bool vis[MAXN];
int pre[MAXN];
void Dijkstra(
int cost[][MAXN],
int lowcost[],
int n,
int beg)
{
for(
int i=
0;i<n;i++)
{
lowcost[i]=INF;
vis[i]=
false;
pre[i]=
1;
}
lowcost[beg]=
0;
for(
int j=
0;j<n;j++)
{
int k = -
1;
int min=INF;
for(
int i=
0;i<n;i++)
{
if(!vis[i]&&lowcost[i]<min)
{
min = lowcost[i];
k=i;
}
}
if(k==-
1)
break;
vis[k]=
true;
for(
int i=
0;i<n;i++)
{
if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
{
lowcost[i]=lowcost[k]+cost[k][i];
pre[i]=k;
}
}
}
}
int lowcost[MAXN];
int cost[MAXN][MAXN];
int main()
{
int N,M;
while(
cin>>N>>M)
{
memset(cost,
0x3f,
sizeof(cost));
int A,B,X;
for(
int i=
0;i<M;i++)
{
scanf(
"%d%d%d",&A,&B,&X);
if(X<cost[A][B])
{
cost[A][B]=X;
cost[B][A]=X;
}
}
int S,T;
cin>>S>>T;
Dijkstra(cost,lowcost,N,S);
if(lowcost[T]==INF)
cout<<-
1<<endl;
else cout<<lowcost[T]<<endl;
}
return 0;
}
