HDUOJ-----2066一个人的旅行

一个人的旅行

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16300    Accepted Submission(s): 5589

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

Author

Grass

Source

RPG专场练习赛

 代码:

 1 /*Problem : 2066 ( 一个人的旅行 )     Judge Status : Accepted
 2 RunId : 10197295    Language : C++    Author : huifeidmeng
 3 Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta*/
 4 #include<stdio.h>
 5 #include<string.h>
 6 const int inf=0x3f3f3f3f;
 7 const int tol=1005;
 8 int path[tol];
 9 int sta[tol][tol],lowc[tol];
10 void Dijkstra(int n,int beg)
11 {
12     int i,j,minc;
13     int vis[tol]={0};
14     vis[beg]=1;
15     for(i=1 ;i<n ;i++)
16     {
17         lowc[i]=sta[beg][i];
18         path[i]=beg;
19     }
20     lowc[beg]=0;
21     path[beg]=-1;
22     int pre=beg;
23     for(i=2; i<n;i++)
24     {
25         minc=inf;
26         for(j=1 ;j<n ;j++)
27         {
28             if(vis[j]==0 && lowc[pre]+sta[pre][j]<lowc[j])
29             {
30                 lowc[j]=lowc[pre]+sta[pre][j];
31                 path[j]=pre;
32             }
33         }
34         for(j=1;j<n;j++)
35         {
36             if(vis[j]==0&&lowc[j]<minc)
37             {
38                 minc=lowc[j];
39                 pre=j;
40             }
41         }
42         vis[pre]=1;
43     }
44 
45 }
46 int main()
47 {
48    int t,s,d,a,b,c,limit,i,j,ans;
49    while(scanf("%d%d%d",&t,&s,&d)!=EOF)
50    {
51        ans=inf;
52        for(i=0;i<tol;i++)
53        {
54            for(j=0;j<tol;j++)
55            {
56                sta[i][j]=inf;
57            }
58        }
59        while(t--)
60        {
61            scanf("%d%d%d",&a,&b,&c);
62            if(sta[a][b]>c||sta[a][b]==0)
63                sta[a][b]=sta[b][a]=c;
64        }
65        for(i=0;i<s;i++)
66        {
67            scanf("%d",&a);
68            //相邻那么距离为0
69            sta[0][a]=sta[a][0]=0;
70        }
71        for(i=0;i<d;i++)
72        {
73            //此处就是中毒,故到n的距离也为0
74            scanf("%d",&a);
75            sta[a][tol-1]=sta[tol-1][a]=0;
76 
77        }
78        Dijkstra(tol,0);
79        printf("%d\n",lowc[tol-1]);
80    }
81     return 0;
82 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏华章科技

全球顶尖公司的烧脑面试题,普通人一道都答不出来!

一些世界知名的企业在招聘时,可能会提供面试智力题,来筛选应聘者。那些越是大牌,越是有名的国内500强,乃至世界500强,给出的面试真是一般人都答不出来。

10020
来自专栏ml

NYOJ------汉诺塔(一)

汉诺塔(一) 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的...

20330
来自专栏算法修养

FZU 2092 收集水晶(记忆化搜索)

Problem 2092 收集水晶 Accept: 101 Submit: 439 Time Limit: 5000 mSec Memory...

28560
来自专栏小樱的经验随笔

HDU 2546 饭卡(01背包裸题)

饭卡 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/O...

31050
来自专栏进击的程序猿

cs224d-第二课-word2vec

首先我想说下为什么会去学习cs224d,原先我一直是做工程的,做了大概3年,产品做了好多,但是大多不幸夭折了,上线没多久就下线,最后实在是经受不住心灵的折磨,转...

18710
来自专栏吉浦迅科技

用超级计算机来验证双幻原子核(double magic nuclei)

美国橡树岭(Oak Ridge National Laboratory)的物理学家用超级计算机确认了镍78是个双幻原子核(double magic nuclei...

34690
来自专栏算法修养

HDU-1166敌兵布阵(线段树)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java...

34040
来自专栏龙行天下CSIEM

科学瞎想系列之六十六 电机定转子极数不同转矩会怎样

搞电机的宝宝们都知道,电机要想实现稳定的机电能量转换,必须满足两个条件,一是定转子极数相等;二是定转子的磁场还要相对静止。这是无数电机界老前辈在他们的书里...

31940
来自专栏AI科技评论

大会 | IJCAI 2018 开幕,中国作者论文占据半壁江山,Jitrenda Malik 获卓越研究奖

AI 科技评论按:继 ICML 2018 之后,同为人工智能/机器学习顶级会议的 IJCAI 2018 也于 7 月 16 日在瑞典斯德哥尔摩开幕。

12220
来自专栏DT数据侠

张翰娜扎为何分手?这个“科学配对实验”已洞穿一切

连张翰娜扎这种外形登对的高颜值组合都宣告分手,圣诞节独守空房的你有什么资格老泪纵横。在这个什么都讲究精准配对的时代,遇不到真爱可能真的是概率问题。

8600

扫码关注云+社区

领取腾讯云代金券