# 一个人的旅行

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

Problem Description

Input

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 }```

657 篇文章64 人订阅

0 条评论

## 相关文章

10020

20330

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

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

28560

31050

18710

34690

34040

31940

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

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

12220

8600