题意：
输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个。 接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路) 。
接着的第T+1行有S个数，表示和草儿家相连的城市。
接着的第T+2行有D个数，表示草儿想去地方。
思路：
需要注意一点，a，b可能有多条路，保存最短路。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 #define INF 1000001 8 9 int T, S, D, n;10 11 int d[1005][1005];12 int e[1005];13 int vis[1005], num[1005];14 15 16 void Dijkstra()17 {18 int min, pos;19 vis[0] = 1;20 for (int i = 0; i <= n; i++)21 num[i] = d[0][i];22 for (int i = 1; i <= n; i++)23 {24 min = INF;25 for (int j = 1; j <= n; j++)26 {27 if (num[j] < min && !vis[j])28 {29 pos = j;30 min = num[j];31 }32 }33 if (min == INF) break;34 vis[pos] = 1;35 for (int j = 1; j <= n; j++)36 {37 if (num[pos] + d[pos][j] < num[j] && !vis[j])38 num[j] = num[pos] + d[pos][j];39 }40 }41 }42 43 int main()44 {45 //freopen("D:\\txt.txt", "r", stdin);46 int a, b, t;47 while (~scanf("%d%d%d", &T, &S, &D))48 {49 n = 0;50 memset(vis, 0, sizeof(vis));51 for (int i = 0; i <= 1005; i++)52 {53 d[i][i] = 0;54 for (int j = i + 1; j <= 1005; j++)55 d[i][j] = d[j][i] = INF;56 }57 58 for (int i = 0; i < T; i++)59 {60 scanf("%d%d%d", &a, &b, &t);61 n = max(n, max(a, b));62 if (t
本来是想用Floyd的，但是不行，超时了。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 #define INF 1000001 8 9 int T, S, D;10 11 int d[1005][1005];12 int e[1005];13 int vis[1005];14 int p[1005];15 16 17 int main()18 {19 //freopen("D:\\txt.txt", "r", stdin);20 int a, b, t;21 while (~scanf("%d%d%d", &T, &S, &D))22 {23 int cnt = 1;24 for (int i = 0; i <= 1000; i++)25 {26 d[i][i] = 0;27 for (int j = i + 1; j <= 1000; j++)28 d[i][j] = d[j][i] = INF;29 }30 p[0] = 0;31 for (int i = 0; i < T; i++)32 {33 scanf("%d%d%d", &a, &b, &t);34 if (!vis[a])35 {36 vis[a] = 1;37 p[cnt++] = a;38 }39 if (!vis[b])40 {41 vis[b] = 1;42 p[cnt++] = b;43 }44 if(t < d[a][b]) d[a][b] = d[b][a] = t;45 }46 47 for (int i = 0; i < S; i++)48 {49 scanf("%d", &a);50 d[0][a] = 0;51 d[a][0] = 0;52 }53 for (int i = 0; i < D; i++)54 scanf("%d", &e[i]);55 56 for (int k = 0; k < cnt; k++)57 for (int i = 0; i < cnt; i++)58 for (int j = 0; j < cnt; j++)59 d[p[i]][p[j]] = min(d[p[i]][p[j]], d[p[i]][p[k]] + d[p[k]][p[j]]);60 61 62 int ans = INF;63 for (int j = 0; j < D; j++)64 ans = min(ans, d[0][e[j]]);65 printf("%d\n", ans);66 67 for (int i = 0; i < cnt; i++)68 vis[p[i]] = 0;69 }70 return 0;71 }