单源最短路径 hdu 2066

#include<string.h> //和prim类似
#include<stdio.h> //prim所考虑的是节点与当前所建成的树的距离最小
using namespace std; //单源最短路径考虑的是节点与出发点距离最小
int vis[1005][1005];
bool boo[1005];
const int maxa=1000000;
struct que{int x,y,len;}
q[1005];
int main()
{
int leng[1005];
int t,s,d,a,b,time;
while(~scanf("%d%d%d",&t,&s,&d)){
memset(boo,0,sizeof(boo));
int MAX=0;
for(int i=0;i<1005;i++){
for(int k=0;k<1005;k++)
vis[i][k]=maxa;
}
for(int i=0;i<t;i++){
scanf("%d%d%d",&a,&b,&time);
if(a>MAX)
MAX=a;
if(b>MAX)
MAX=b;
if(vis[a][b]>time){
vis[a][b]=time;
vis[b][a]=time;
}
}
for(int i=0;i<=1005;i++){
leng[i]=maxa;
}
for(int i=0;i<s;i++){
scanf("%d",&a);
leng[a]=0;
}
for(int i=0;i<=MAX;i++){
int ii,mina=maxa;
for(int k=0;k<=MAX;k++){
if(boo[k]==0&&leng[k]<mina){
mina=leng[k];
ii=k;
}
}
boo[ii]=1;
for(int i=0;i<=MAX;i++){
if(leng[i]>leng[ii]+vis[ii][i])
leng[i]=leng[ii]+vis[ii][i];
}
}
int mina=maxa;
for(int i=0;i<d;i++){
scanf("%d",&a);
if(mina>leng[a])
mina=leng[a];
}
printf("%d\n",mina);
}
}

巴特西

单源最短路径 hdu 2066

最新文章

热门文章