[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;

}

巴特西