一个人的旅行
Time Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8364Accepted Submission(s): 2863
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
#include<stdio.h>
#include<string.h>
int map[1005][1005],used[1005],n,m,start[1005],end[1005],max,min[1005];
void init()
{
int i,j;
for(i=1;i<=1003;i++)
for(j=1;j<=1003;j++)
if(i!=j) map[i][j]=999999999;
else map[i][j]=0;
}
void find_short(int s)
{
int i,j,mm,pos;
memset(used,0,sizeof(used));
for(i=1;i<=max;i++)
min[i]=map[s][i];
min[s]=0;
used[s]=1;
for(i=2;i<=max;i++)
{
mm=999999999;
for(j=1;j<=max;j++)
if(!used[j]&&mm>min[j])
{
pos=j;
mm=min[j];
}
if(mm==999999999) break;//剪枝 很好的 节省好多时间的 啊
used[pos]=1;
for(j=1;j<=max;j++)
if(!used[j]&&min[pos]+map[pos][j]<min[j])
min[j]=min[pos]+map[pos][j];
}
}
int main()
{
int i,j,endnum,x,y,t,ans,startnum;
while(scanf("%d %d %d",&m,&startnum,&endnum)!=EOF)
{
init();
max=0;ans=999999999;
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&t);
if(x>max) max=x;
if(y>max) max=y;
if(map[x][y]>t)
map[y][x]=map[x][y]=t;//一开始只是给map[x][y]赋了值 好二逼啊 WA了2次
}
for(i=1;i<=startnum;i++)
{
scanf("%d",&start[i]);
if(max<start[i]) max=start[i];
}
for(i=1;i<=endnum;i++)
{
scanf("%d",&end[i]);
if(max<end[i]) max=end[i];
}
for(i=1;i<=startnum;i++)
{
find_short(start[i]);
for(j=1;j<=endnum;j++)
{
if(ans>min[end[j]]) ans=min[end[j]];
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
杭电ACMhdu1163
hdu1001解题报告
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
hdu 1574 passed sorce
这个是杭电hdu的一个分类,新手们可以按照这个来刷题!
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
自己做的HDU ACM已经AC的题目
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
Hdu 1237 解题代码