Problem Description 虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。
Input 输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个； 接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=front = 0;Q->reat = 0;return ;}//返回Q的元素个数，也就是队列当前长度int QueueLength(SqQueue Q){return (Q.reat - Q.front + MAXSIZE) % MAXSIZE;}//若队列未满，则插入元素e为Q新队尾元素Status EnQueue(SqQueue *Q, QElemType e){if ((Q->reat + 1) % MAXSIZE == Q->front){return ;}Q->data[Q->reat] = e;Q->reat = (Q->reat + 1) % MAXSIZE;return ;}//若队列不空，则删除Q中队头元素Status DeQueue(SqQueue *Q){if (Q->front == Q->reat){return ;}Q->front = (Q->front + 1) % MAXSIZE;return ;}void init(){//初始化为-1memset(map, -1, sizeof(map));edgeNum = 0;return ;}void add(int a, int b, int time){struct node E = {a, b, time, head[a]};edge[edgeNum] = E;head[a] = edgeNum++;return ;}//佛洛依德算法，最短路void spfa(int neiCity){SqQueue Q;InitQueue(&Q);memset(vis, 0, sizeof(vis));memset(map, 0x3f, sizeof(map));vis[neiCity] = 1;map[neiCity] = 0;EnQueue(&Q, neiCity);while (QueueLength(Q)){int u = Q.front, i;DeQueue(&Q);vis[u] = 0;for (i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (map[v] > map[u] + edge[i].time){map[v] = map[u] + edge[i].time;if (!vis[v]){vis[v] = 1;EnQueue(&Q, v);}}}}return ;}int main(){int T, S, D;int a, b, time;int neiCity[MAXSIZE], goCity[MAXSIZE];int i, j, min;while (~scanf("%d %d %d", &T, &S, &D)){init();while (T--){scanf("%d %d %d", &a, &b, &time);add(a, b, time);add(b, a, time);//双向图}for (i = 0; i < S; i++){scanf("%d", neiCity + i);}for (i = 0; i < D; i++){scanf("%d", goCity + i);}min = INF;for (i = 0; i < S; i++){spfa(neiCity[i]);for (j = 0; j < D; j++){if (min > map[goCity[j]]){min = map[goCity[j]];}}}printf("%d\n", min);}return 0;}
floyd：
#include#include #define MAXSIZE 1000#define INF 0x3f3f3f3f //表示无穷大#define MAX(a, b) a > b ? a : b#define MIN(a, b) a < b ? a : bint map[MAXSIZE][MAXSIZE];void init(){//初始化为无穷大memset(map, 0x3f, sizeof(map));for (int i = 1; i < MAXSIZE; i++){map[i][i] = 0;}return ;}//佛洛依德算法，最短路void floyd(int n){int i, j, k;for (k = 1; k time){map[a][b] = map[b][a] = time;}n = MAX(MAX(n, a), b);}for (i = 0; i < S; i++){scanf("%d", neiCity + i);}for (i = 0; i < D; i++){scanf("%d", goCity + i);}floyd(n);min = INF;for (i = 0; i < S; i++){for (j = 0; j < D; j++){min = MIN(min, map[i][goCity[j]]);}}printf("%d\n", min);}return 0;}如果用C写的话，建议用第二种，毕竟第一种需要用到队列，而队列需要自己去实现。好处是，自己写的队列可以进行优化，将不必要的功能删去。