C++之路进阶codevs1269（匈牙利游戏）

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 ﬁrst 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：

样例输出2：

数据范围及提示 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.

题解

两遍spfa，然后枚举起点终点（所必走的边），取次小，因为是严格次短，所以可以这样YY掉

  1 #include<cstdio>
  2 #include<queue>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #define maxn 100000+10
  7 #define INF 0x7fffffff
  8 
  9 using namespace std;
 10 
 11 struct ss
 12   {
 13        int to,next,edge; 
 14   }e_t[maxn<<1],e_f[maxn<<1];
 15   
 16 struct sss
 17   {
 18       int t,f;
 19       void add(int x)
 20         {
 21             t=x; f=x;
 22         }
 23   }dis[maxn];
 24 
 25 int head_t[maxn],head_f[maxn],cnt_t,cnt_f,vis[maxn];
 26 
 27 void insert_t(int u,int v,int edge)
 28       {
 29           e_t[++cnt_t].next=head_t[u];
 30           e_t[cnt_t].to=v;
 31           e_t[cnt_t].edge=edge;
 32           head_t[u]=cnt_t;
 33       }
 34 
 35 void insert_f(int u,int v,int edge)
 36      {
 37           e_f[++cnt_f].next=head_f[u];
 38           e_f[cnt_f].to=v;
 39           e_f[cnt_f].edge=edge;
 40           head_f[u]=cnt_f;
 41       }
 42 
 43 void spfa_t(int x)
 44    {
 45         queue<int>que;
 46         que.push(x);
 47         vis[x]=1;dis[x].t=0;
 48         while (!que.empty())
 49            {
 50                  int now=que.front();que.pop();vis[now]=0;
 51                  for (int i=head_t[now];i;i=e_t[i].next)
 52                     if (dis[e_t[i].to].t>dis[now].t+e_t[i].edge)
 53                      {
 54                           dis[e_t[i].to].t=dis[now].t+e_t[i].edge;
 55                           if (!vis[e_t[i].to]) que.push(e_t[i].to),vis[e_t[i].to]=1;
 56                      }
 57            }
 58    }
 59 
 60 void spfa_f(int x)
 61    {
 62         queue<int>que;
 63         que.push(x);
 64         vis[x]=1;dis[x].f=0;
 65         while (!que.empty())
 66            {
 67                  int now=que.front();que.pop();vis[now]=0;
 68                  for (int i=head_f[now];i;i=e_f[i].next)
 69                     if (dis[e_f[i].to].f>dis[now].f+e_f[i].edge)
 70                      {
 71                           dis[e_f[i].to].f=dis[now].f+e_f[i].edge;
 72                           if (!vis[e_f[i].to]) que.push(e_f[i].to),vis[e_f[i].to]=1;
 73                      }
 74            }
 75    }
 76 
 77 int n,m;
 78       
 79 int main()
 80    {
 81         scanf("%d%d",&n,&m);
 82      for (int i=1;i<=m;i++)
 83         {
 84           int x,y,z;
 85           scanf("%d%d%d",&x,&y,&z);
 86           insert_t(x,y,z),insert_f(y,x,z);
 87         }
 88      for (int i=1;i<=n;i++) dis[i].add(INF);     
 89         spfa_t(1);spfa_f(n);
 90         int ans=INF,sans=-1;
 91         for (int i=1;i<=n;i++)
 92                for (int j=head_t[i];j;j=e_t[j].next)
 93                  {
 94                    if (dis[i].t!=INF&&dis[e_t[j].to].f!=INF&&ans>dis[e_t[j].to].f+dis[i].t+e_t[j].edge)
 95                         sans=ans,ans=dis[e_t[j].to].f+dis[i].t+e_t[j].edge;
 96                    if (dis[i].t!=INF&&dis[e_t[j].to].f!=INF&&ans<dis[e_t[j].to].f+dis[i].t+e_t[j].edge&&dis[e_t[j].to].f+dis[i].t+e_t[j].edge<sans)
 97                   sans=dis[e_t[j].to].f+dis[i].t+e_t[j].edge;       
 98                  }
 99      if (sans==INF) cout<<-1<<endl; else cout<<sans<<endl;           
100      return 0;
101    }