Input
输入数据有多组，每组的第一行是三个整数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个数，表示草儿想去地方。
Output
输出草儿能去某个喜欢的城市的最短时间。
Sample Input
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
Sample Output
9
Author
Grass
Source
Recommend
lcy | We have carefully selected several similar problems for you: 2544 2112 1217 1548 1142
题目分析：
这道题没什么好说的，一个简单的dijkstra 都快把我做哭了。
#include<cstdio> #include<cstring> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int mark[1010],cost[1010][1010],dis[1010]; int e[1010],s[1010]; int N,n,m,t; void dijkstra(int s) { memset(mark,0,sizeof(mark)); memset(dis,INF,sizeof(dis)); dis[s]=0; while(1) { int v=-1; for(int i=1;i<=1000;i++) if(!mark[i]&&(v==-1||dis[i]<dis[v])) v=i; if(v==-1) break; mark[v]=1; for(int i=1;i<=1000;i++) dis[i]=min(dis[i],dis[v]+cost[v][i]); } } int main() { while(~scanf("%d%d%d",&n,&m,&t)) { N=0; memset(cost,INF,sizeof(cost)); while(n--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(cost[a][b]>c) cost[a][b]=cost[b][a]=c; if(a==b) cost[a][a]=0; N=max(N,max(a,b));// 这记录一下最大编号 在查路径是用能节省时间 不过直接查到1000 也过了 } for(int i=1;i<=m;i++) scanf("%d",&s[i]); for(int i=1;i<=t;i++) scanf("%d",&e[i]); int min=INF; for(int i=1;i<=m;i++) { dijkstra(s[i]); for(int j=1;j<=t;j++) { if(dis[e[j]]<min) min=dis[e[j]];// 错了几十遍就错在 e[j] 写成 e[i] 真想剁手 妈的 } } printf("%d\n",min); } return 0; }
