一个人的旅行
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;
}
分享到:
相关推荐
在有向或无向图G=(V,E)中,每条边e=(u,v)都关联一个非负权重w(e),最短路问题就是找出从源节点s到目标节点t的路径,使得这条路径上的边的权重之和最小。如果图中的权重代表距离,那么最短路就是实际意义上的最短路径...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
通过学习和分析"HDU最全ac代码",你可以学到以下几个方面的知识: 1. **基础算法**:包括排序算法(快速排序、归并排序、堆排序等)、搜索算法(深度优先搜索、广度优先搜索、A*搜索等)、图论算法(最短路径、最小...
总的来说,"HDU DP动态规划"是一个关于使用动态规划解决HDU平台上某一题目的主题,它要求掌握动态规划的基本概念、方法,并能灵活应用到实际问题中,同时可能涉及到文件交互和调试,以完成问题的求解。
具体地,题目涉及到了斐波那契数列的一个变种:F(1)=1, F(2)=1, F(3)=1, F(4)=1, F(n>4)=F(n-1)+F(n-2)+F(n-3)+F(n-4),其中n > 4。这里的关键是要能够计算出F(n)的值,而由于这个序列的增长速度非常快,传统的整数...
HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案。这里的“java实现”意味着作者使用Java作为编程工具来解答这些算法题。 在Java编程方面,以下是一些可能涵盖的知识点: 1. ...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。...ACM HDU 题目分类是一个非常重要的参考资源,对于编程选手来说,掌握这些分类可以帮助他们更好地理解和解决问题。
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
HDU1059的代码
hdu1001解题报告
【标签】"ACM题解 HDU"意味着这是一个关于如何解答HDU ACM题目的资源,可能包含了解题思路、算法解析、代码实现等方面的内容。这样的资料对于准备ACM比赛的选手或者希望提升算法能力的程序员来说非常有价值。 在...
【标签】:“杭电”代表题目来源于杭州电子科技大学,是ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest, ICPC)比赛的一个平台,提供了许多供学生练习和参赛的题目。"ACM"是此类竞赛的...
代码读取输入的整数`n`表示测试用例的数量,然后对每个测试用例,读取一个字符串`str`,并将它的后半部分移到前面,形成新的字符串`s`,最后输出结果。 3. HDU 2084 - 数组操作 这是一个涉及数组操作的问题。代码...
hdu 1574 passed sorce
题目背景设置在一个充满想象力的情境下,即如何通过不同数量的切刀将一个球形蛋糕分割成尽可能多的部分,以此激发读者的思考兴趣。 #### 题目描述 题目要求计算当在一个球体(本题中的蛋糕)上切割 _n_ 刀时(每一...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
HDU ACM(ACM/ICPC国际大学生程序设计竞赛)是一个知名的编程竞赛平台,它提供了大量的算法题目供参赛者挑战。这些题目旨在提升参赛者的算法设计、编程和问题解决能力。"hdu acm2000至2099参考源码"是针对这个平台上...
hdu2101AC代码
动态规划的关键在于确定状态转移方程,即如何从前一个或前几个状态转移到当前状态。 ### 知识点详解 #### Robberies (抢劫) 题目链接:[Robberies](http://acm.hdu.edu.cn/showproblem.php?pid=2955) - **问题...