1269 匈牙利游戲 2012年CCC加拿大高中生信息學奧賽

1269 匈牙利游戲

2012年CCC加拿大高中生信息學奧賽

Welcome to the Hungary Games! The streets of Budapest form a twisted network of one-way streets.

歡迎來到匈牙利游戲！佈達佩斯（匈牙利首都）的街道形成了一個彎曲的單向網路。

You have been forced to join a race as part of a “Reality TV” show where you race through these streets, starting at the Sz´echenyi thermal bath (s for short) and ending at the Tomb of G¨ ul Baba (t for short).

你被強制要求參加一個賽跑作為一個TV秀的一部分節目，比賽中你需要穿越這些街道，從s開始，到t結束。

Naturally, you want to complete the race as quickly as possible, because you will get more promo- tional contracts the better you perform.

很自然的，你想要儘快的完成比賽，因為你的比賽完成的越好，你就能得到更多的商業促銷合同。

However, there is a catch: any person who is smart enough to take a shortest s-t route will be thrown into the P´alv¨olgyi cave system and kept as a national treasure. You would like to avoid this fate, but still be as fast as possible. Write a program that computes a strictly-second-shortest s-t route.

但是，有一個需要瞭解的是，如果有人過於聰明找到從s到t的最短路線，那麼他就被扔到國家極品人類保護系統中作為一個國家寶藏收藏起來。你顯然要避免這種事情的發生，但是也想越快越好。寫一個程式來計算一個從s到t的嚴格次短路線吧。

Sometimes the strictly-second-shortest route visits some nodes more than once; see Sample Input 2 for an example.

有的時候，嚴格次短路線可能訪問某些節點不止一次。樣例2是一個例子。

The first line will have the format N M, where N is the number of nodes in Budapest and M is the number of edges. The nodes are 1,2,...,N; node 1 represents s; node N represents t. Then there are M lines of the form A B L, indicating a one-way street from A to B of length L. You can assume that A != B on these lines, and that the ordered pairs (A,B) are distinct.

第一行包含兩個整數N和M，N代表佈達佩斯的節點個數，M代表邊的個數。節點編號從1到N。1代表出發點s，N代表終點t。接下來的M行每行三個整數A B L，代表有一條從A到B的長度為L的單向同路。你可以認為A不等於B，也不會有重覆的(A,B)對。

Output the length of a strictly-second-shortest route from s to t. If there are less than two possible lengths for routes from s to t, output −1.

輸出從s到t的嚴格次短路的長度。如果從s到t的路少於2條，輸出-1。

樣例輸入1：

4 6

1 2 5

1 3 5

2 3 1

2 4 5

3 4 5

1 4 13

樣例輸入2：

2 2

1 2 1

2 1 1

樣例輸出1：

11

樣例輸出2：

3

對於樣例1：

There are two shortest routes of length 10 (1 → 2 → 4,1 → 3 → 4) and the strictly-second- shortest route is 1 → 2 → 3 → 4 with length 11.

對於樣例2：

The shortest route is 1 → 2 of length 1, and the strictly-second route is 1 → 2 → 1 → 2 of length 3.

分類標簽 Tags 點此展開

求次短路的問題

註意spfa中的三條註釋

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int MAXN=100001;
 7 const int maxn=0xfffffff;
 8 struct node
 9 {
10     int u;
11     int v;
12     int w;
13     int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 int n,m;
18 int dis[MAXN];
19 int vis[MAXN];// 是否在隊列中 
20 int tot=0;
21 int pre[MAXN];// 記錄次短路 
22 void spfa()
23 {
24     dis[1]=0;
25     vis[1]=1;
26     queue<int>q;
27     q.push(1);
28     while(q.size()!=0)
29     {
30         int p=q.front();
31         q.pop();
32         vis[p]=0;
33         for(int i=head[p];i!=-1;i=edge[i].next)
34         {
35             int to=edge[i].v;
36             if(dis[to]>dis[p]+edge[i].w)
37             {
38                 pre[to]=dis[to];// 記錄下更新之前的長度 即次長 
39                 dis[to]=dis[p]+edge[i].w;
40                 //if(edge[i].v==n)tot++;
41                 if(vis[to]==0)
42                 {
43                     q.push(to);
44                     vis[to]=1;
45                 }
46             }
47             else if(dis[to]!=dis[p]+edge[i].w&&pre[to]>dis[p]+edge[i].w)
48             {
49                 pre[to]=dis[p]+edge[i].w;// 根據條件，此時需要更新，否則就不是次短路 
50                 if(vis[to]==0)
51                 {
52                     q.push(to);
53                     vis[to]=1;
54                 }
55             }
56             if(pre[to]>pre[p]+edge[i].w)// 同理，需要更新 
57             {
58                 pre[to]=pre[p]+edge[i].w;
59                 if(vis[to]==0)
60                 {
61                     q.push(to);
62                     vis[to]=1;
63                 }
64             }
65         }
66     }
67 }
68 int main()
69 {
70     scanf("%d%d",&n,&m);
71     for(int i=1;i<=n;i++)
72     {
73         head[i]=-1;
74         dis[i]=maxn;
75         pre[i]=maxn;
76     }
77     for(int i=1;i<=m;i++)
78     {
79         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
80         edge[num].next=head[edge[num].u];
81         head[edge[num].u]=num++;
82     }
83     spfa();
84     if(pre[n]!=maxn)
85     printf("%d",pre[n]);
86     else
87     {
88         printf("-1");
89     }
90     return 0;
91 }