一个人的旅行
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5994 Accepted Submission(s): 1995
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
一道很简单的最短路,是求从起点到喜欢的点的最短路中的最短那个,spfa或者dijk都能求-从起点到任意点的最短距离,我用spfa搞定!
代码:
#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;
}
分享到:
相关推荐
最短路(HDU-2544).rar
HDU最全ac代码
HDU的一题........HDU DP动态规
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
这个是杭电hdu的一个分类,新手们可以按照这个来刷题!
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了