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.

次短路裸题

是单向边,本蒟蒻傻不拉几的用双向边坐了半天、、、、(竟然还有分。。。ORZ)

我们要建反向边,因为我们在反着跑spfa的时候要用到反向边、、、、

#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 510000
#define maxn 99999999
using namespace std;
bool vis[N];
int n,m,x,y,z,sum,ans,tot,d1[N],d2[N],head[N],head1[N];
queue<int>q;
struct Edge
{
    int to,dis,from,next;
}edge[N<<],edge1[N<<];
int add(int x,int y,int z)
{
    tot++;
    edge[tot].to=y;
    edge[tot].dis=z;
    edge[tot].next=head[x];
    head[x]=tot;
    edge1[tot].to=x;
    edge1[tot].dis=z;
    edge1[tot].next=head1[y];
    head1[y]=tot;
}
int read()
{
    ,f=; char ch=getchar();
    ; ch=getchar();}
    +ch-'; ch=getchar();}
    return x*f;
}
int spfa(int s,int *dis,int *head,Edge *edge)
{
    ;i<=n;i++) dis[i]=maxn,vis[i]=false;
    vis[s]=; q.push(s);
    while(!q.empty())
    {
        int x=q.front();q.pop();vis[x]=false;
        for(int i=head[x];i;i=edge[i].next)
        {
            int t=edge[i].to;
            if(dis[t]>dis[x]+edge[i].dis)
            {
                dis[t]=dis[x]+edge[i].dis;
                if(!vis[t]) vis[t]=true,q.push(t);
            }
        }
    }
}
int main()
{
    n=read(),m=read();
    ;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        add(x,y,z);
     }
    spfa(,d1,head,edge),spfa(n,d2,head1,edge1);
    ans=maxn;
    ;i<=n;i++)
     for(int j=head[i];j;j=edge[j].next)
     {
         int t=edge[j].to;
         sum=d1[i]+d2[t]+edge[j].dis;
         if(sum>d1[n]&&sum<ans) ans=sum;
     }
    if(ans==maxn) printf("-1\n");
    else printf("%d",ans);
    ;
}

最新文章

  1. vagrant 1.8.6 安装过程及总结遇到的坑
  2. Java中怎么切换窗口
  3. 微信h5页面禁止下拉露出网页来源
  4. 应用的启动视图 LauchView
  5. laravel 加中间件的方法 防止直接打开后台
  6. linux下的mount命令的用法详解
  7. tomcat生产部署关键参数设置
  8. CopyOnWriteArrayList你都不知道,怎么拿offer?
  9. angularjs兼容thickbox 插件
  10. js 统计字符串中字符出现的次数
  11. Day03 - Ruby比一比:Module的include与extend
  12. (转)MySql中监视增删改查和查看日志记录
  13. TCP的三次握手和四次挥手图解
  14. Qt Creator插件Todo
  15. Hibernate Validator实践之一 入门篇
  16. iOS: 计算 UIWebView 的内容高度
  17. 在cygwin下安装ns2
  18. cat /etc/init.d/nfs 这句话看不懂
  19. Centos7安装Redis4.0.8
  20. STL源码剖析(set/map)

热门文章

  1. lavarel功能总结
  2. ssh 非root用户互信
  3. codeforces 235 B lets play osu!
  4. PHP08 数组和数据结构
  5. HDU - 5438 Ponds(拓扑排序删点+并查集判断连通分量)
  6. 标准库中的智能指针shared_ptr
  7. CF-478C
  8. Java实现深拷贝和浅拷贝
  9. LINUX:关于Redis集群的节点分配
  10. Python旅途——函数(1)