HDU 2680

 1 /*
 2 使用pair代替结构
 3 */
 4 
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <queue>
 8 #include <vector>
 9 using namespace std;
10 const int Ni = 1010;
11 const int INF = 0x3f3f3f3f;
12 
13 typedef pair<int,int> pa;
14 
15 int dis[Ni],n;//dis使用1-n的部分
16 
17 vector<pair<int,int> > eg[Ni];
18 
19 void Dijkstra(int s)
20 {
21           int i,j;
22           for(i=1;i<=n;i++)//要到n
23                     dis[i] = INF;
24           priority_queue<pa> q;  //优先级队列：小顶堆
25           dis[s] = 0;
26           q.push(make_pair(s,dis[s]));
27 
28           while(!q.empty())
29           {
30                     pa x = q.top();
31                     q.pop();
32                     int w = x.first;
33                     for(j = 0;j<eg[w].size();j++)//遍历x的所有邻接点
34                     {
35                               pa y = eg[w][j];//y是x的邻接点
36                               int u = y.first;
37                               if(dis[u]>x.second+y.second)
38                               {
39                                         dis[u] = x.second+y.second;
40                                         q.push(make_pair(u,dis[u]));
41                               }
42                     }
43           }
44 
45 }
46 
47 
48 int main()
49 {
50           int m,a,b,y,d,min;//关系个数
51           while(cin>>n>>m>>y)
52           {
53                     for(int i = 0;i<=n;i++)
54                               eg[i].clear();//初始化
55                     while(m--)
56                     {
57                               cin>>a>>b>>d;
58                               eg[b].push_back(make_pair(a,d));
59                     }
60 
61                     Dijkstra(y);
62 
63                     int t,x;
64                     min = INF;
65                     cin>>t;
66                     while(t--)
67                     {
68                               cin>>x;
69                               if(dis[x]<min)
70                                         min = dis[x];
71                     }
72                     if(min!=INF)
73                               cout<<min<<endl;
74                     else
75                               cout<<"-1\n";
76           }
77 
78           return 0;
79 }