一个人的旅行
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5889 Accepted Submission(s): 1966
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
Dijkstra算法:参考文章:http://www.wutianqi.com/?p=1890
此题参考文章:http://blog.csdn.net/allenjy123/article/details/5998854
#include <iostream>
using namespace std;
const int MAX = 1010;
const int INF = 99999999;
int pre[MAX]; //记录当前节点的前一个节点
int dist[MAX]; //记录当前点到源点的最短时间
int c[MAX][MAX]; //记录两城市之间的时间
bool hash[MAX]; //记录当前节点是否被处理
int L; //节点数
int max(int a, int b)
{
return a > b ? a : b;
}
int Dijkstra(int start, int end)
{
int i, min;
for(i = 0; i <= L; i++)
{
hash[i] = true;
dist[i] = INF;
pre[i] = -1;
}
hash[0] = false;
dist[0] = 0;
while(start != end)
{
for(i = 0; i <= L; i++)
{
if(c[start][i])
{
if(dist[i] > dist[start] + c[start][i])
{
dist[i] = dist[start] + c[start][i];
pre[i] = start;
}
}
}
min = INF;
for(i = 0; i <= L; i++)
{
if(min > dist[i] && hash[i])
{
min = dist[i];
start = i;
}
}
hash[start] = false;
}
return dist[end];
}
//打印路径,栈操作
void searchPath(int p)
{
if(p != 0)
searchPath(pre[p]);
else
return;
cout <<p;
if(p != pre[L])
cout<<"->";
else
cout << endl;
}
int main()
{
int t, s, d, a, b, time, i;
while(cin >> t >> s >> d)
{
memset(c, 0, sizeof(c)); //先对时间进行初始化
L = 0;
for(i = 1; i <= t; i++)
{
cin >> a >> b >> time;
if(!c[a][b])
c[a][b] = c[b][a] = time;
else
{
if(c[a][b] > time) //有多条路径保存最短的 比如 a -> b 也可以由 a -> c -> b
c[a][b] = time;
}
if(L < max(a, b))
L = max(a, b);
}
//输入起点
for(i = 1; i <= s; i++)
{
cin >> a;
c[0][a] = c[a][0] = 1;
}
L++;
//输入终点
for(i = 1; i <= d; i++)
{
cin >> a;
c[L][a] = c[a][L] = 1;
}
//注意这多加了2,所以结果要减2
cout << Dijkstra(0, L) - 2 << endl;
searchPath(pre[L]);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu题目分类
自己做的HDU ACM已经AC的题目
HDU图论题目分类
hdu 1005.比较简单的一道题,有兴趣的可以看看。