输入输出样例
输入样例#1： 复制
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例#1： 复制
7
说明
【样例说明】
5->6->1->4 (3 + 1 + 3)
#include<stdio.h>
#define N 3000
int e[N][N],book[N],dis[N];
int main()
{
int a,b,c,i,j,u,v,n,m,s,t,min,inf=99999999;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
e[i][j]=0;
else
e[i][j]=inf;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(e[a][b]>c)
e[a][b]=e[b][a]=c;
}
for(i=1;i<=n;i++)
book[i]=0;
book[s]=1;
for(i=1;i<=n;i++)
dis[i]=e[s][i];
for(i=1;i<n;i++)
{
min=inf;
for(j=1;j<=n;j++)
if(book[j]==0&&dis[j]<min)
{
min=dis[j];
u=j;
}
book[u]=1;
for(v=1;v<=n;v++)
if(dis[v]>dis[u]+e[u][v]&&e[u][v]!=inf)
dis[v]=dis[u]+e[u][v];
}
printf("%d\n",dis[t]);
return 0;
}
