最短路 || HDU 2066 一个人的旅行

本草的旅行故事(✺ω✺)，可以从S个点中的任意一个开始，到达D个点中的任意一个，求最短路

*解法：把草儿的家记成点0，S个点与0的距离为0，然后spfa求最短路

又是改了一万次，①多组数据啊 ②改完多组数据记得加初始化啊 ③无向图反着也要建啊

脑子可能被我丢在被窝里了zzzzZ

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 using namespace std;
 6 #define SZ 20005
 7 #define INF 1e9+10
 8 int head[SZ],nxt[SZ],tot = 0;
 9 struct edge
10 {
11     int t,d;
12 }l[SZ];
13 void build(int f,int t,int d)
14 {
15     l[++tot] = (edge){t,d};
16     nxt[tot] = head[f];
17     head[f] = tot;
18 }
19 queue<int> q;
20 bool use[SZ];
21 int dist[SZ];
22 void spfa(int s)
23 {
24     memset(dist, 63, sizeof(dist));
25     memset(use, 0, sizeof(use));
26     use[s] = 1;
27     dist[s] = 0;
28     q.push(s);
29     while(!q.empty())
30     {
31         int u = q.front(); q.pop();
32         use[u] = 0;
33         for(int i = head[u];i;i = nxt[i])
34         {
35             int v = l[i].t;
36             if(dist[v] > dist[u] + l[i].d)
37             {
38                 dist[v] = dist[u] + l[i].d;
39                 if(!use[v])
40                     use[v] = 1, q.push(v);
41             }
42         }
43     }
44     return;
45 }
46 int main()
47 {
48     int T, S, D;
49     while(scanf("%d %d %d", &T, &S, &D) != EOF)
50     {
51         memset(head, 0, sizeof(head));
52         tot = 0;
53         for(int i = 0; i < T; i++)
54         {
55             int x, y, z;
56             scanf("%d %d %d", &x, &y, &z);
57             build(x, y, z);
58             build(y, x, z);
59         }
60         for(int i = 0;i < S; i++)
61         {
62             int x;
63             scanf("%d", &x);
64             build(0, x, 0);
65             build(x, 0, 0);//反着也要建
66         }
67         spfa(0);
68         int minn = INF;
69         for(int i = 0; i < D; i++)
70         {
71             int ed;
72             scanf("%d", &ed);
73             minn = min(minn, dist[ed]);
74         }
75         printf("%d
", minn);
76     }
77     return 0;
78 }