【wikioi】1269ハンガリーゲーム(サブショート+spfa)
5452 ワード
http://www.wikioi.com/problem/1269/
ふふ、思いもよらなかった..
ショートはたるんだときに手足を作ることです.
d 1を最短、d 2を二次短絡とする
あります
d 1[v]>d 1[u]+w(u,v)は明らかにd 1を更新するが、d 1は最短であるため、明らかにd 2が元のd 1に等しくなってからd 1を更新する
d 2[v]>d 1[u]+w(u,v)&&d 1[v]>d 1[u]+w(u,v)現在d 1[u]+w(u,v)は最短ではないが、二次短絡よりも小さいため、二次短絡を更新することは明らかである
d 2[v]>d 2[u]+w(u,v)この場合、二次短絡は二次短絡よりも短いので、必ず二次短絡を更新する
テーマ説明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).
テレビショーの一部として競走に参加するように強制され、試合中はこれらの街を通り抜け、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.
場合によっては、厳格な短いルートでは、いくつかのノードに1回以上アクセスすることがあります.サンプル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.
第1行は2つの整数NとMを含み、Nはブダペストのノード個数を表し、Mはエッジの個数を表す.ノード番号は1からNまでです.1は出発点sを表し、Nは終点tを表す.次のM行の各行の3つの整数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.
ふふ、思いもよらなかった..
ショートはたるんだときに手足を作ることです.
d 1を最短、d 2を二次短絡とする
あります
d 1[v]>d 1[u]+w(u,v)は明らかにd 1を更新するが、d 1は最短であるため、明らかにd 2が元のd 1に等しくなってからd 1を更新する
d 2[v]>d 1[u]+w(u,v)&&d 1[v]>d 1[u]+w(u,v)現在d 1[u]+w(u,v)は最短ではないが、二次短絡よりも小さいため、二次短絡を更新することは明らかである
d 2[v]>d 2[u]+w(u,v)この場合、二次短絡は二次短絡よりも短いので、必ず二次短絡を更新する
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }
const int N=20005, M=100005, oo=1000000000;
int d1[N], d2[N], q[N+N], front, tail, ihead[N], cnt, n, m, vis[N];
struct ED { int to, next, w; } e[M];
inline void add(const int &u, const int &v, const int &w) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; e[cnt].w=w; }
int spfa() {
for1(i, 1, n) d1[i]=d2[i]=oo;
tail=front=d1[1]=0; vis[1]=q[tail++]=1;
int u, v, w;
while(tail!=front) {
u=q[front++]; if(front==N-5) front=0;
for(int i=ihead[u]; i; i=e[i].next) {
v=e[i].to, w=e[i].w;
if(d1[v]>d1[u]+w) {
d2[v]=d1[v]; d1[v]=d1[u]+w;
if(!vis[v]) { vis[v]=1; q[tail++]=v; if(tail==N-5) tail=0; }
}
else if(d2[v]>d1[u]+w && d1[u]+w>d1[v]) {
d2[v]=d1[u]+w;
if(!vis[v]) { vis[v]=1; q[tail++]=v; if(tail==N-5) tail=0; }
}
if(d2[v]>d2[u]+w) {
d2[v]=d2[u]+w;
if(!vis[v]) { vis[v]=1; q[tail++]=v; if(tail==N-5) tail=0; }
}
}
vis[u]=0;
}
if(d2[n]==oo) return -1;
return d2[n];
}
int main() {
read(n); read(m);
int x, y, z;
rep(i, m) {
read(x); read(y); read(z);
add(x, y, z);
}
printf("%d
", spfa());
return 0;
}
テーマ説明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).
テレビショーの一部として競走に参加するように強制され、試合中はこれらの街を通り抜け、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.
場合によっては、厳格な短いルートでは、いくつかのノードに1回以上アクセスすることがあります.サンプル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.
第1行は2つの整数NとMを含み、Nはブダペストのノード個数を表し、Mはエッジの個数を表す.ノード番号は1からNまでです.1は出発点sを表し、Nは終点tを表す.次のM行の各行の3つの整数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.