求次短路 codevs 1269 匈牙利遊戲

codevs 1269 匈牙利遊戲

2012年CCC加拿大高中生資訊學奧賽

 時間限制: 1 s

 空間限制: 128000 KB

 題目等級 : 鑽石 Diamond

題目描述 Description

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是一個例子。

輸入描述 Input Description

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 Description

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。

樣例輸入 Sample Input

樣例輸入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

樣例輸出 Sample Output

樣例輸出1：

11

樣例輸出2：

3

資料範圍及提示 Data Size & Hint

對于樣例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.

1 /*直接利用SPFA維護一個點到另一個點的最短路和次短路，維護方法如下：
 2 1、如果from的最短路能更新to的最短路，就讓更新之前的最短路等于次短路，然後去更新最短路。 
 3 2、如果from的最短路不能跟新to的最短路，但是可以更新次短路，就去更新次短路。 
 4 3、如果form的最短路不能跟新to的最短路，也不能更新次短路，但是from的次短路可以更新to的次短路，那麼就去更新次短路。
 5 
 6 */
 7 #include<algorithm>
 8 #include<queue>
 9 #include<iostream>
10 using namespace std;
11 #include<cstdio>
12 #define N 50010
13 #define inf (1<<30)-1
14 bool inque[N]={0};
15 int n,m,a,b,l;
16 long long dis[N],cdis[N];
17 int head[N];
18 struct Edge{
19     int v,w,last;
20 }edge[1000000];
21 int t=0;
22 void add_edge(int u,int v,int w)
23 {
24     ++t;
25     edge[t].v=v;
26     edge[t].w=w;
27     edge[t].last=head[u];
28     head[u]=t;
29 }
30 void input()
31 {
32     cin>>n>>m;
33     //scanf("%d%d",&n,&m);
34     for(int i=1;i<=m;++i)
35     {
36         cin>>a>>b>>l;
37         //scanf("%d%d%d",&a,&b,&l);
38         add_edge(a,b,l);
39     }
40     for(int i=1;i<=n;++i)
41       dis[i]=cdis[i]=inf;
42 }
43 void spfa(int k)
44 {
45     queue<int>Q;
46     Q.push(k);
47     inque[k]=true;
48     dis[k]=0;//
49     while(!Q.empty())
50     {
51         int x=Q.front();
52         Q.pop();
53         inque[x]=false;
54         for(int l=head[x];l;l=edge[l].last)
55         {
56             if(dis[x]+edge[l].w<dis[edge[l].v])
57             {
58                 cdis[edge[l].v]=dis[edge[l].v];
59                 dis[edge[l].v]=dis[x]+edge[l].w;
60                 if(!inque[edge[l].v])
61                 {
62                     inque[edge[l].v]=true;
63                     Q.push(edge[l].v);
64                 }
65             }
66             else if(edge[l].w+dis[x]>dis[edge[l].v]&&dis[x]+edge[l].w<cdis[edge[l].v])//
67                  {
68                      cdis[edge[l].v]=dis[x]+edge[l].w;
69                      if(!inque[edge[l].v])
70                     {
71                     inque[edge[l].v]=true;
72                     Q.push(edge[l].v);
73                     }
74                  }
75             else if(cdis[edge[l].v]>cdis[x]+edge[l].w)//
76             {
77                 cdis[edge[l].v]=cdis[x]+edge[l].w;
78                 if(!inque[edge[l].v])
79                     {
80                     inque[edge[l].v]=true;
81                     Q.push(edge[l].v);
82                     }
83             }
84         }
85     }
86 }
87 int main()
88 {
89     input();
90     spfa(1);
91     if(cdis[n]==inf) cout<<-1;
92     else cout<<cdis[n]<<endl; 
93     return 0;
94 }