Problem Description
虽然草儿是个路痴 (就是在杭电待了一年多, 居然还会在校园里迷路的人, 汗~), 但是草儿仍然很喜欢旅行, 因为在旅途中 会遇见很多人 (白马王子,^0^), 很多事, 还能丰富自己的阅历, 还可以看美丽的风景...... 草儿想去很多地方, 她想要去东京铁塔看夜景, 去威尼斯看电影, 去阳明山上看海芋, 去纽约纯粹看雪景, 去巴黎喝咖啡写信, 去北京探望孟姜女...... 眼看寒假就快到了, 这么一大段时间, 可不能浪费啊, 一定要给自己好好的放个假, 可是也不能荒废了训练啊, 所以草儿决定在要在最短的时间去一个自己想去的地方! 因为草儿的家在一个小镇上, 没有火车经过, 所以她只能去邻近的城市坐火车 (好可怜啊~).
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
详细代码如下:
- /*
- 1. 定义一个邻接矩阵 map, 存放各点间最短路径
- 2. 定义一个数组 home, 存放邻近家的地点
- 3. 定义一个数组 visit, 存放想去的地方
- 4. 改写 dijkstra, 形如: int dijkstra(int map[][],int p,int visit[]);
- 使其返回起点到想去地方的最短距离
- 5. 定义一个数组 minDis, 存放各个 dijksrta 的返回值
- 6. 选出 minDis 中最小的值, 输出
- */
- /*
- 输入数据有多组, 每组的第一行是三个整数 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 个数, 表示草儿想去地方.
- */
- #include <stdio.h>
- #include <string.h>
- #define INF 2000000000 // 一定要足够大
- #define MAX 100
- int dijkstra(int map[MAX][MAX],int p,int visit[],int d);
- int main()
- {
- int t,s,d;
- int a,b,time;
- int map[MAX][MAX];
- int home[MAX];
- int visit[MAX];
- int minDis[MAX];
- int minD;
- int i,j;
- while (~scanf("%d%d%d",&t,&s,&d))
- {
- if (t==0)
- break;
- for (i=1; i<MAX; i++) // 将邻接矩阵初始化为 INF
- for (j=1; j<MAX; j++)
- map[i][j] = INF;
- for (i=1; i<=t; i++) // 更新邻接矩阵的值
- {
- scanf("%d%d%d",&a,&b,&time);
- if (map[a][b]>time) // 选取两点之间最短路径
- map[a][b] = map[b][a] = time;
- }
- for (i=1; i<=s; i++) // 输入 s 个邻近家的地方
- scanf("%d",&home[i]);
- for (i=1; i<=d; i++) // 输入 d 个想去的地方
- scanf("%d",&visit[i]);
- for (i=1; i<=s; i++) // 将邻近家的地方依次作为起点
- {
- minDis[i] = dijkstra(map,home[i],visit,d);
- }
- minD = minDis[1];
- for (i=2; i<=s; i++) // 从各个不同的起点到目的地的最小距离中再选出最小的
- if (minD>minDis[i])
- minD = minDis[i];
- printf("%d\n",minD); // 输出
- }
- return 0;
- }
- int dijkstra(int map[MAX][MAX],int p,int visit[],int d)
- {
- int dist[MAX];
- int s[MAX];
- int minDist = INF;
- int mint;
- int t;
- int temp;
- int i,j;
- for (i=1; i<MAX; i++)
- dist[i] = map[p][i];
- memset(s,0,MAX*sizeof(int));
- s[p] = 1;
- dist[p] = 0;
- for (i=1; i<MAX; i++)
- {
- mint = INF;
- t = p;
- for (j=1; j<MAX; j++)
- if (mint>dist[j]&&!s[j])
- {
- mint = dist[j];
- t = j;
- }
- s[t] = 1;
- for (j=1; j<MAX; j++)
- if (!s[j]&&map[t][j]<INF)
- if (dist[t]+map[t][j]<dist[j])
- dist[j] = dist[t]+map[t][j];
- }
- for (i=1; i<=d; i++)
- {
- temp = visit[i];
- if (dist[temp]<minDist)
- minDist = dist[temp];
- }
- return minDist;
- }
来源: https://www.cnblogs.com/WeiTaoHu/p/9903751.html