本文共 1841 字，大约阅读时间需要 6 分钟。
#include#include #include #include #include using namespace std;const int maxn = 1000 + 5;const int INF = 0xffffff;struct node{ int next; int len; int to;} edge[maxn * 10];int sign[maxn];int dis[maxn];int connect[maxn];int t, s, d, a, b, time, pos, min_time;int Start[maxn];int End[maxn];inline void add_edge(int op, int ed, int len){ edge[pos].next = connect[op]; edge[pos].len = len; edge[pos].to = ed; connect[op] = pos; pos ++;}int SPFA(int op, int ed){ queue process; memset(sign, 0, sizeof(sign)); for(int i = 0; i < maxn; i ++) dis[i] = INF; dis[op] = 0; process.push(op); sign[op] = 1; while(!process.empty()) { int temp_op = process.front(); process.pop(); sign[temp_op] = 0; for(int i = connect[temp_op]; i != -1; i = edge[i].next) { int temp_ed = edge[i].to; int temp_len = edge[i].len; if(dis[temp_op] + temp_len < dis[temp_ed]) { dis[temp_ed] = dis[temp_op] + temp_len; if(!sign[temp_ed]) { process.push(temp_ed); sign[temp_ed] = 1; } } } } return dis[ed];}int main(){ while(~scanf("%d %d %d", & t, & s, & d)) { memset(connect, -1, sizeof(connect)); pos = 0; while(t --) { scanf("%d %d %d", & a, & b, & time); add_edge(a, b, time); add_edge(b, a, time); } for(int i = 0; i < s; i ++) scanf("%d", & Start[i]); for(int i = 0; i < d; i ++) scanf("%d", & End[i]); min_time = INF; for(int i = 0; i < s; i ++) for(int j = 0; j < d; j ++) min_time = min(min_time, SPFA(Start[i], End[j])); printf("%d\n", min_time); } return 0;}
题意：
草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车。
输入数据有多组，每组的第一行是三个整数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个数，表示草儿想去地方。 输出草儿能去某个喜欢的城市的最短时间。题解：
练习SPFA。
转载地址：http://pctpi.baihongyu.com/