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> #include<string.h> #include<algorithm> #define inf 0xffffff #define min(a,b) a>b?b:a #define max(a,b) a>b?a:b using namespace std; int map[1010][1010],dis[1010],visit[1010]; int maxn; int a1[1010],s1[1010]; void dijstra(int x) { int i,j,min,sum=0,pos=x; memset(visit,0,sizeof(visit)); for(i=1;i<=maxn;++i) { dis[i]=map[x][i]; } visit[x]=1; dis[x]=0;///// for(i=1;i<maxn;++i) { min=inf; for(j=1;j<=maxn;++j) { if(!visit[j]&&min>dis[j]) { min=dis[j]; pos=j; } } sum+=min; //// visit[pos]=1; // if(min==inf)/// // return ; for(j=1;j<=maxn;++j) { if(!visit[j]&&dis[j]>dis[pos]+map[pos][j]) dis[j]=dis[pos]+map[pos][j]; } } } int main() { int i,j,t,s,d,a,b,c; while(~scanf("%d%d%d",&t,&s,&d)) { maxn=0; for(i=1;i<1010;++i) { for(j=1;j<1010;++j) map[i][j]=inf; } for(i=1;i<=t;++i) { scanf("%d%d%d",&a,&b,&c); maxn=max(max(a,b),maxn); if(c<map[a][b]) map[a][b]=map[b][a]=c; } for(i=1;i<=s;++i) { scanf("%d",&s1[i]); maxn=max(s1[i],maxn);///同下 } for(i=1;i<=d;++i) { scanf("%d",&a1[i]); maxn=max(a1[i],maxn);//此处必须加上否则会WA } int min=inf; for(i=1;i<=s;++i) { dijstra(s1[i]); for(j=1;j<=d;++j) { min=min(min,dis[a1[j]]); } } printf("%d\n",min); } return 0; }
原文:http://blog.csdn.net/ice_alone/article/details/44699735