[AHOI2017初中组]guide

题目描述

农场主John最近在网上买了一辆新车，在购买汽车配件时，John不小心点了两次“提交”按钮。导致汽车上安装了两套GPS系统，更糟糕的是John在使用GPS导航时，两套系统常常给出不同的路线。从地图上看，John居住的地区有N(2 ≤ N ≤ 100,000)个十字路口和M(1 ≤ M ≤ 500,000)条限定通行方向的道路。第i条道路连接路口 A_i (1 ≤ A_i ≤ N)和B_i (1 ≤ B_i ≤ N)，两个路口之间可能连接有多条道路。允许双向通?的道路是将两条单向通?的道路隔开所形成的。

John的家在路口1位置，农场在路口N的位置。John可以沿着?系列单向道路从家驾车到农场。所有GPS系统的底层地图信息都是?样的，区别仅在于对每一条道路的通?时间计算不同。对于第i条道路第一套GPS系统计算通行时间为P_i个单位时间，而第二套GPS系统则给出Q_i个单位时间。（所有道路的通行时间都是范围在1到100，000之间的整数）John想要驾车从家到农场。可是，一路上GPS系统总是不厌其烦的提醒John（请从路口X开往路口Y），这是由于John选取了某套GPS系统建议的路径，而另一套GPS系统则认为这不是从路口X到农场的最短路径。我们称之为GPS系统的抱怨。

请你计算一下如果John选择合适的路径到达农场能听到的最少GPS系统的抱怨数 。如果John经过某条道路两套GPS系统都发出抱怨，则抱怨总数加2。

输入格式

第一行，两个整数N和M。

接下来M行，其中第i行描述了道路i的信息，A_i B_i P_i Q_i。

输出格式

一个整数，表示John一路上能听到的最小抱怨数。

三次最短路，反向建边

求2种权值的最短路，即为任意点到n的距离

第三次把边权换掉，得出走一条边抱怨次数，跑最短路，输出dis3[1]

if(dis1[u]+w1[i]!=dis1[v])y++;

if(dis2[u]+w2[i]!=dis2[v])y++;

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int  long long
using namespace std;
const long long N=4e5+10,M=5*N,inf=1<<29;
int next[M],head[N],go[M],w1[M],w2[M],tot;
inline void add(int u,int v,int o1,int o2){
    next[++tot]=head[u];head[u]=tot;go[tot]=v;w1[tot]=o1;w2[tot]=o2;
}
int n,m;
queue<int>q;
int dis1[N],dis2[N],dis3[N];
bool vis[N];
inline void dj1(int s){
    for(int i=1;i<=n;i++)dis1[i]=inf;
    q.push(s);
    dis1[s]=0;
    while(q.size()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=next[i]){
            int v=go[i];
            if(dis1[v]>dis1[u]+w1[i]){
                dis1[v]=dis1[u]+w1[i];
                if(!vis[v])q.push(v),vis[v]=1;
            }
        }
    }
}
inline void dj2(int s){
    for(int i=1;i<=n;i++)dis2[i]=inf;
    q.push(s);
    dis2[s]=0;
    while(q.size()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=next[i]){
            int v=go[i];
            if(dis2[v]>dis2[u]+w2[i]){
                dis2[v]=dis2[u]+w2[i];
                if(!vis[v])q.push(v),vis[v]=1;
            }
        }
    }
}
inline void dj3(int s){
    for(int i=1;i<=n;i++)dis3[i]=inf;
    q.push(s);
    dis3[s]=0;
    while(q.size()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=next[i]){
            int v=go[i],y=0;
            if(dis1[u]+w1[i]!=dis1[v])y++;
            if(dis2[u]+w2[i]!=dis2[v])y++;
            if(dis3[v]>dis3[u]+y){
                dis3[v]=dis3[u]+y;
                if(!vis[v])q.push(v),vis[v]=1;
            }
        }
    }
}
signed main(){
    
    cin>>n>>m;
    for(int i=1,u,v,o1,o2;i<=m;i++){
        scanf("%lld%lld%lld%lld",&u,&v,&o1,&o2);
        add(v,u,o1,o2);
    }
    
    dj1(n),dj2(n);

    dj3(n);
    cout<<dis3[1]<<endl;
}

[AHOI2017初中组]guide

原文：https://www.cnblogs.com/naruto-mzx/p/11612187.html