原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=2066
分析：超级源点+SPFA。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<vector> 7 #include<queue> 8 #define ll long long 9 #define inf 0xfffffff 10 #define maxn 1005 11 using namespace std; 12 struct edge 13 { 14 int to,time; 15 edge (int x,int y) 16 { 17 to=x;time=y; 18 } 19 }; 20 vector<edge>e[maxn]; 21 int T,S,D,d[maxn]; 22 bool vis[maxn]; 23 queue<int>q; 24 void spfa(int s) 25 { 26 while(!q.empty())q.pop(); 27 for(int i=0;i<maxn;i++) 28 { 29 d[i]=inf;vis[i]=false; 30 } 31 d[0]=0; 32 vis[0]=true; 33 q.push(0); 34 while(!q.empty()) 35 { 36 int u=q.front();q.pop(); 37 for(int i=0;i<e[u].size();i++) 38 { 39 if(d[e[u][i].to]>d[u]+e[u][i].time) 40 { 41 d[e[u][i].to]=d[u]+e[u][i].time; 42 if(!vis[e[u][i].to]){ 43 vis[e[u][i].to]=true; 44 q.push(e[u][i].to); 45 } 46 } 47 } 48 vis[u]=false; 49 } 50 } 51 int main() 52 { 53 while(~scanf("%d%d%d",&T,&S,&D)) 54 { 55 for(int i=0;i<maxn;i++)e[i].clear(); 56 int u,v,t; 57 for(int i=0;i<T;i++) 58 { 59 scanf("%d%d%d",&u,&v,&t); 60 e[u].push_back(edge(v,t)); 61 e[v].push_back(edge(u,t)); 62 } 63 for(int i=0;i<S;i++) 64 { 65 scanf("%d",&u); 66 e[0].push_back(edge(u,1)); 67 e[u].push_back(edge(0,1)); 68 } 69 spfa(0); 70 int ans=inf; 71 for(int i=0;i<D;i++) 72 { 73 scanf("%d",&u); 74 ans=min(ans,d[u]); 75 } 76 printf("%d ",ans-1); 77 } 78 return 0; 79 }