codevs——1269 匈牙利(Hungary)游玩

分类标签 Tags 点此进行

求次短路的难点

只顾spfa中的三条注释

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int MAXN=100001;
 7 const int maxn=0xfffffff;
 8 struct node
 9 {
10     int u;
11     int v;
12     int w;
13     int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 int n,m;
18 int dis[MAXN];
19 int vis[MAXN];// 是否在队列中 
20 int tot=0;
21 int pre[MAXN];// 记录次短路 
22 void spfa()
23 {
24     dis[1]=0;
25     vis[1]=1;
26     queue<int>q;
27     q.push(1);
28     while(q.size()!=0)
29     {
30         int p=q.front();
31         q.pop();
32         vis[p]=0;
33         for(int i=head[p];i!=-1;i=edge[i].next)
34         {
35             int to=edge[i].v;
36             if(dis[to]>dis[p]+edge[i].w)
37             {
38                 pre[to]=dis[to];// 记录下更新之前的长度 即次长 
39                 dis[to]=dis[p]+edge[i].w;
40                 //if(edge[i].v==n)tot++;
41                 if(vis[to]==0)
42                 {
43                     q.push(to);
44                     vis[to]=1;
45                 }
46             }
47             else if(dis[to]!=dis[p]+edge[i].w&&pre[to]>dis[p]+edge[i].w)
48             {
49                 pre[to]=dis[p]+edge[i].w;// 根据条件,此时需要更新,否则就不是次短路 
50                 if(vis[to]==0)
51                 {
52                     q.push(to);
53                     vis[to]=1;
54                 }
55             }
56             if(pre[to]>pre[p]+edge[i].w)// 同理,需要更新 
57             {
58                 pre[to]=pre[p]+edge[i].w;
59                 if(vis[to]==0)
60                 {
61                     q.push(to);
62                     vis[to]=1;
63                 }
64             }
65         }
66     }
67 }
68 int main()
69 {
70     scanf("%d%d",&n,&m);
71     for(int i=1;i<=n;i++)
72     {
73         head[i]=-1;
74         dis[i]=maxn;
75         pre[i]=maxn;
76     }
77     for(int i=1;i<=m;i++)
78     {
79         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
80         edge[num].next=head[edge[num].u];
81         head[edge[num].u]=num++;
82     }
83     spfa();
84     if(pre[n]!=maxn)
85     printf("%d",pre[n]);
86     else
87     {
88         printf("-1");
89     }
90     return 0;
91 }

 

1269 匈牙利(Hungary)游戏

 

2013年CCC加拿大高级中学生音讯学国际学科奥林匹克比赛

 时限: 1
s

 空间范围: 12七千KB

 标题品级 : 钻石
Diamond

题解

 

 

 

主题素材陈述 Description

Welcome to the Hungary Games! The streets of Budapest form a twisted
network of one-way streets.

应接来到匈牙利娱乐!汉堡(匈牙利(Magyarország)都城)的街道形成了贰个弯盘曲曲的单向网络。

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.

一对时候,严俊次短路径或许访问一些节点不唯有三回。样例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

样例输出 萨姆ple 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.

 

次短路裸题

是单向边,本虎掌傻不拉几的用双向边坐了半天、、、、(竟然还应该有分。。。OHighlanderZ)

作者们要建反向边,因为我们在反着跑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<<1],edge1[N<<1];
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()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int spfa(int s,int *dis,int *head,Edge *edge)
{
    for(int i=1;i<=n;i++) dis[i]=maxn,vis[i]=false;
    vis[s]=true,dis[s]=0; 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();
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        add(x,y,z);
     } 
    spfa(1,d1,head,edge),spfa(n,d2,head1,edge1);
    ans=maxn;
    for(int i=1;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);
    return 0;
}

 

分类标签 Tags 点此进行 

 

最短路 图论 CCC加拿大高级中学生音讯学奥赛 大陆以外 2012年

 

一种思路:

凶残次短路难点(无法重复最短路做次短路) 

二种意况
1.最短路能够被最短路更新,次短路能够被更新前的最短路更新
2.最短路不能够革新,次短路能够被更新
3.次绿灯能够被次短路更新

调治的时候或许会油然则生以下情况,小编也不知道为啥,但实在能够AC。

图片 1

  AC代码1:

#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int N=1e5+10;
int tot,next[N<<1],head[N];
int pre[N],dis[N];
bool vis[N];
struct node{
    int v,w;
}e[N];
inline void add(int x,int y,int z){
    e[++tot].v=y;e[tot].w=z;next[tot]=head[x];head[x]=tot;
}
deque<int>q;//双端队列 
void spfa(int s){
    memset(dis,0x3f,sizeof dis);//初始化一个极大值,不然不给过QAQ别问我怎么知道的
    memset(pre,0x3f,sizeof pre);
    memset(vis,0,sizeof vis);
    q.push_back(0); 
    q.push_back(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop_front();
        vis[u]=0;
        for(int i=head[u];i;i=next[i]){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                pre[v]=dis[v];//更新后的最短路是最短路,更新之前的最短路是当前的次短路
                dis[v]=dis[u]+e[i].w;
                if(dis[v]<dis[q.front()]) 
                    q.push_front(v);
                else 
                    q.push_back(v);
            }//如果可以更新最短路,那么就让它更新吧
            else if(pre[v]>dis[u]+e[i].w&&dis[v]<dis[u]+e[i].w){
                pre[v]=dis[u]+e[i].w;
                if(dis[v]<dis[q.front()]) 
                    q.push_front(v);
                else 
                    q.push_back(v);
            }//如果不能更新最短路,但是可以更新次短路,那么就让它更新吧
            else if(pre[v]>pre[u]+e[i].w){
                pre[v]=pre[u]+e[i].w;
                if(dis[v]<dis[q.front()]) 
                    q.push_front(v);
                else 
                    q.push_back(v);
            }//次短路可以更新次短路,那么就让它更新吧
        }
    } 
}
int main(){
    int n,m,x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z);
    spfa(1);    
    printf("%d\n",pre[n]>0&&pre[n]<1061109567?pre[n]:-1);    
    return 0;
}

 来自题解思路的AC代码:(调节和测量检验无不胜)

 AC代码2:

/*
   从前向后spfa一遍,再把边反向spfa一遍,求出dis1和dis2
   枚举每条边,设这条边一定要走,求出这种情况下的最短路,最后在所有情况中找出严格次短路
   对于这个方法的理解:
   因为如果求不出严格次短路,说明严格次短路中的某条路没有走过,那么我们可以让这条路一定走,
   那么经过这条路的最短路一定是严格次短路,所以要把所有的点枚举一遍
   注意:这个方法求不出次短路,因为如果这样做,最短路可能走过两遍,但我们是分辨不出来的,
   这对本题没有影响,因为严格次短路的长度与最短路不同,但次短路可能与最短路长度相同,
   所以不对。 
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 100010
#define M 20010
struct node{
    int v,w,next;
}e1[N<<1],e2[N<<1];
int n,m,cnt,t1,t2,f[N<<2],head1[M],head2[M],dis1[M],dis2[M];
bool vis[M];
inline void add1(int x,int y,int z){
    e1[++t1].v=y;e1[t1].w=z;e1[t1].next=head1[x];head1[x]=t1;
}
inline void add2(int x,int y,int z){
    e2[++t2].v=y;e2[t2].w=z;e2[t2].next=head2[x];head2[x]=t2;
}
inline void spfa1(){
    memset(dis1,63,sizeof dis1);
    memset(vis,0,sizeof vis);
    vis[1]=1;
    dis1[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty()){
        int p=q.front();q.pop();
        vis[p]=0;
        for(int i=head1[p];i;i=e1[i].next){
            int v=e1[i].v,w=e1[i].w;
            if(dis1[v]>dis1[p]+w){
                dis1[v]=dis1[p]+w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    } 
}
inline void spfa2(){
    memset(dis2,63,sizeof dis2);
    memset(vis,0,sizeof vis);
    vis[n]=1;
    dis2[n]=0;
    queue<int>q;
    q.push(n);
    while(!q.empty()){
        int p=q.front();q.pop();
        vis[p]=0;
        for(int i=head2[p];i;i=e2[i].next){
            int v=e2[i].v,w=e2[i].w;
            if(dis2[v]>dis2[p]+w){
                dis2[v]=dis2[p]+w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    } 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),add1(x,y,z),add2(y,x,z);
    spfa1();spfa2();
    for(int i=1;i<=n;i++){
        for(int j=head1[i];j;j=e1[j].next){
            f[++cnt]=dis1[i]+e1[j].w+dis2[e1[j].v];
        }
    }
    sort(f+1,f+cnt+1);
    for(int i=2;i<=cnt;i++) if(f[i]>f[1]&&f[i]<1061110972){printf("%d",f[i]);return 0;}
    printf("-1");
    return 0;
}

 

 

 

PS:

主旨做的是严谨次短路

对于次短路

发表评论

电子邮件地址不会被公开。 必填项已用*标注