hdu 2066 一个人的旅行（起点到任意点的最短路）

一个人的旅行

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5994????Accepted Submission(s): 1995

#include <iostream>#include <stdio.h>#include <memory.h>#include <queue>#include <algorithm>using namespace std;const int INF = 99999999;const int N = 1005;int map[N][N], dist[N], g[N];bool visit[N];int t, s, d;void init() //初始化函数{ int i, j; for(i = 0; i < N; i++) for(j = 0; j < N; j++) if(i == j) map[i][j] = 0; else map[i][j] = INF;}void input() //输入函数{ int i, k, ti, tj, cost; while(t--) { scanf("%d %d %d", &ti, &tj, &cost); //输入两点距离 if(cost < map[ti][tj]) map[ti][tj] = map[tj][ti] = cost; } for(i = 0; i < s; i++) //与家相邻的距离为0 { scanf("%d", &k); map[0][k] = map[k][0] = 0; } for(i = 0; i < d; i++) //输入想去的地方 scanf("%d", &g[i]);}void spfa() //spfa求起点到所有其它点的最短路{ int i, now; memset(visit, false, sizeof(visit)); for(i = 0; i < N; i++) dist[i] = INF; dist[0] = 0; queue<int> Q; Q.push(0); visit[0] = true; while(!Q.empty()) { now = Q.front(); Q.pop(); visit[now] = false; for(i = 0; i < N; i++) { if(dist[i] > dist[now] + map[now][i]) { dist[i] = dist[now] + map[now][i]; if(visit[i] == false) { Q.push(i); visit[i] = true; } } } }}int main(){ int i, MIN; while(scanf("%d %d %d", &t, &s, &d) != EOF) { init(); input(); spfa(); MIN = INF; for(i = 0; i < d; i++) //找所有想去的点中最短的 { if(dist[g[i]] < MIN) MIN = dist[g[i]]; } printf("%d\n", MIN); } return 0;}