codevs 1269 匈牙利游戏——次短路（spfa）-白红宇

codevs 1269 匈牙利游戏——次短路（spfa）

阅读量：6652 次

发布时间：2019-06-25

本文共 1674 字，大约阅读时间需要 5 分钟。

　欢迎来到匈牙利游戏！布达佩斯（匈牙利首都）的街道形成了一个弯曲的单向网络。

你被强制要求参加一个赛跑作为一个TV秀的一部分节目，比赛中你需要穿越这些街道，从s开始，到t结束。

很自然的，你想要尽快的完成比赛，因为你的比赛完成的越好，你就能得到更多的商业促销合同。

但是，有一个需要了解的是，如果有人过于聪明找到从s到t的最短路线，那么他就被扔到国家极品人类保护系统中作为一个国家宝藏收藏起来。

你显然要避免这种事情的发生，但是也想越快越好。写一个程序来计算一个从s到t的严格次短路线吧。

有的时候，严格次短路线可能访问某些节点不止一次。样例2是一个例子。

输入描述 Input Description

　　第一行包含两个整数N和M，N代表布达佩斯的节点个数，M代表边的个数。

　　　节点编号从1到N。1代表出发点s，N代表终点t。

　　接下来的M行每行三个整数A B L，代表有一条从A到B的长度为L的单向同路。

　　你可以认为A不等于B，也不会有重复的(A,B)对。

输出描述 Output Description

　　输出从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

　样例输出1：

　样例输入2：

　2 2

　1 2 1

　2 1 1

　样例输出2：

————————————————————————

一道裸的严格次短路分三类就好辣

存一波代码（八成也没什么人看

#include
        
         #include
         
          #include
          
           #include
           
            #define LL long longusing namespace std;const int M=20007;const LL inf=1e15;LL read(){    LL ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
      if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int n,m;int first[M],cnt;struct node{
      int to,next; LL w;}e[250007];void ins(int a,int b,LL w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}LL d1[M],d2[M];int vis[M];queue
            
             q;void spfa(){    for(int i=1;i<=n;i++) d1[i]=d2[i]=inf;    d1[1]=0; vis[1]=0; q.push(1);    while(!q.empty()){        int x=q.front(); q.pop();        for(int i=first[x];i;i=e[i].next){            bool f=false;            int now=e[i].to;            if(d1[x]+e[i].w
             
              d1[now]&&d1[x]+e[i].w