6 2 3 1 3 5 1 4 7 2 8 12 3 8 4 4 9 12 9 10 2 1 2 8 9 10
9
#include<stdio.h>
int map[1100][1100];
int ok[1100];
int now[1100];
int sta[1100];
int end[1100];
#define max 1007
int main()
{
int t,s,d;
int i,j,k;
int nowlen,nowx;
int a,b,l;
int ans;
while(scanf("%d%d%d",&t,&s,&d)!=EOF)
{
for(i=1;i<=max;i++)
for(j=1;j<=max;j++)
map[i][j]=max;//map初始为无穷大
for(i=1;i<=t;i++)
{
scanf("%d%d%d",&a,&b,&l);
if(map[a][b]>l)
map[a][b]=map[b][a]=l;
}//更新给定的距离
for(i=1;i<=s;i++)
scanf("%d",&sta[i]);
for(i=1;i<=d;i++)
scanf("%d",&end[i]);
for(i=1;i<=s;i++)
{//for循环迪杰斯特拉
for(j=1;j<=max;j++)
{
now[j]=max;
ok[j]=0;
}
now[sta[i]]=0;
ok[sta[i]]=1;//初始now和ok
for(k=1;k<=max;k++)
{
nowlen=max;
for(j=1;j<=max;j++)
{
if(!ok[j]&&nowlen>map[sta[i]][j])
{
nowlen=map[sta[i]][j];
nowx=j;
}
}//找到还没确定的距离之中最小的距离
now[nowx]=nowlen;
ok[nowx]=1;
for(j=1;j<=max;j++)
{
if(!ok[j]&&map[sta[i]][j]>now[nowx]+map[nowx][j])
map[sta[i]][j]=now[nowx]+map[nowx][j];
}//更新其他点到原点的距离
}
}
ans=max;
for(i=1;i<=s;i++)
for(j=1;j<=d;j++)
if(map[sta[i]][end[j]]<ans)
ans=map[sta[i]][end[j]];//找到最小的
printf("%d\n",ans);
}
return 0;
}版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/wangluoershixiong/article/details/46997961