一个人的旅行
Problem Description
虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,
因为在旅途中 会遇见很多人(白马王子,^0^),很多事,还能丰富自己的阅历,还可以看美丽的风景……草儿想去很多地方,
她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽约纯粹看雪景,去巴黎喝咖啡写信,去北京探望孟姜女……
眼看寒么一大段时间,可不能浪费啊,假就快到了,这一定要给自己好好的放个假,可是也不能荒废了训练啊,
所以草儿决定在要在最短的时间去一个自己想去的地方!
因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车(好可怜啊~)。
http://acm.hdu.edu.cn/showproblem.php?pid=2066
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
RPG专场练习赛
Recommend
lcy | We have carefully selected several similar problems for you: 2544 1874 2112 1217 1548
/*
思路:
题目考察最短路径问题,但是题目中有一些小变化。
建表的时候,注意和她的家相邻的点要设为0,然后题目就变成了从0站点到终点的几个点最短距离问题
*/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
| #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std;
const int INF = 0x3f3f3f3f;
int map[1001][1001]; int vis[1001]; int dis[1001]; int start[1001], direction[1001]; int n;
void dijkstra(int x){ memset(vis, 0, sizeof(vis)); memset(dis, INF, sizeof(dis)); dis[x] = 0; vis[x] = 0; for(int i=1; i<=n; i++){ for (int j = 1; j<=n; j++){ if(!vis[j] && dis[j] > map[x][j] + dis[x]) dis[j] = map[x][j] + dis[x]; } int minn = INF; for (int j = 1; j<=n; j++){ if(!vis[j] && dis[j]<minn){ minn = dis[j]; x = j; } } vis[x] = 1; } }
int main(){ int T, S, D; while(scanf("%d%d%d",&T,&S,&D)!=EOF){ n = 0; for (int i = 0; i <= 1001; i++){ for (int j = 0; j <= 1001; j++){ if(i==j) map[i][j] = 0; else map[i][j] = INF; } } int a, b, time; for (int i = 0; i < T; i++){ scanf("%d%d%d", &a, &b, &time); n = max(max(a, b), n); if(map[a][b]>time) map[a][b] = map[b][a] = time; } for (int i = 0; i<S; i++){ scanf("%d", &start[i]); map[0][start[i]] = map[start[i]][0] = 0; } for(int i=0; i<D; i++){ scanf("%d", &direction[i]); } dijkstra(0); int mi = INF; for (int i = 0; i < D; i++){ mi = min(dis[direction[i]], mi); } printf("%d\n", mi); } return 0; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std;
const int INF = 0x3f3f3f3f;
int map[1001][1001]; int start[1001], direction[1001];
int main(){ int T, S, D; while(scanf("%d%d%d",&T,&S,&D)!=EOF){ int n = 0; for (int i = 0; i <= 1001; i++){ for (int j = 0; j <= 1001; j++){ if(i==j) map[i][j] = 0; else map[i][j] = INF; } } int a, b, time; for (int i = 0; i < T; i++){ scanf("%d%d%d", &a, &b, &time); n = max(max(a, b), n); if(map[a][b]>time) map[a][b] = map[b][a] = time; } memset(start, 0, sizeof(start)); memset(direction, 0, sizeof(direction)); int temp; for (int i = 0; i<S; i++){ scanf("%d", &temp); start[temp] = 1; } for(int i=0; i<D; i++){ scanf("%d", &temp); direction[temp] = 1; } int mi = INF; for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { if(map[i][k]==INF) continue; for(int j=1;j<=n;j++) { if(i==j) continue; if(map[i][k]+map[k][j]<map[i][j]) map[i][j]=map[j][i]=map[i][k]+map[k][j]; if(start[i] && direction[j] && mi>map[i][j]) mi = map[i][j]; } } } printf("%d\n", mi); } return 0; }
|