[USACO14OPEN]GPS的决斗Dueling GPS's

题目概况

题目描述

给你一个(N)个点的有向图,可能有重边.

有两个(GPS)定位系统,分别认为经过边(i)的时间为(P_i),和(Q_i).

每走一条边的时候,如果一个系统认为走的这条边不是它认为的最短路,就会受到警告一次.

两个系统是分开警告的,就是说当走的这条边都不在两个系统认为的最短路范围内,就会受到2次警告.

如果边((u,v))不在(u)到(n)的最短路径上，这条边就受到一次警告，求从(1)到(n)最少受到多少次警告。

输入格式

第一行,两个整数,(n,m),表示(n)个点,(m)条边.

接下来有(m)行,每一行四个整数,(a_i,b_i,c_i,d_i).

表示有一条有向边((a_i,b_i)),然后第一个导航认为消耗时间为(c_i),第二导航认为消耗时间为(d_i)

输出格式

一行整数,输出最少警告数

数据范围

算法解析

题意理解

1. 两个(GPS),系统为你分别规划了一条最短路径.

2. 一旦你不走其中一个(GPS)认为的最短路径上的边,就会警告你一次.

3. 因此有可能两个(GPS)都警告你.

算法解析

首先,我们要找到两条最短路径.

1. 因此我们需要知道任意节点到(n)号节点的最短路.

2. 所以我们可以建反向图，从(n)号节点出发,分别按照两个GPS跑一次最短路,求出路径.

其次就是统计每条边上警告数量。

1. 我们可以考虑枚举每一条边.

2. 然后针对两个不同的GPS系统

3. 判断其权值是否是这条边两个节点的最短路长度。

4. 如果是表示位于最短路,否则不位于最短路.

最后,统计最少警告数量

1. 根据上面的每条边的警告数量,再来一次最短路.

2. 然后这道题目就解决完了,但是代码是真的一言难尽.

代码解析

#include<bits/stdc++.h>
using namespace std;
const int N=11000;
struct node
{
	int v,w;
};
vector<node> f[N],g[N],ans[N];
int dis1[N],dis2[N],dis3[N],n,m,vis[N];
void spfa(vector<node> g[N],int d[],int x)//传入存储图的数组,最短路数组,起始点
{
	for(int i=1; i<=n; i++)//记住这里一定不能使用memset,因为会失灵
		d[i]=0x3f3f3f3f;
	memset(vis,0,sizeof(vis));//这里可以memset,是因为是全局变量
	d[x]=0;
	queue<int> q;
	q.push(x);
	while (q.size())
	{
		int x=q.front();
		q.pop();
		vis[x]=0;
		for (int i=0; i<g[x].size(); i++)//访问所有的出边
		{
			int y=g[x][i].v,w=g[x][i].w;
			if (d[y]>d[x]+w)//三角形不等式,然后开始松弛
			{
				d[y]=d[x]+w;
				if (!vis[y])
				{
					q.push(y);
					vis[y]=1;
				}
			}
		}
	}
}
inline void init()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		f[b].push_back({a,c});//这里是反向图建立,第一个导航
		g[b].push_back({a,d});//记得将方向取反,第二个导航
	}
	spfa(f,dis1,n);//分别找到GPS距离
	spfa(g,dis2,n);
	for (int i=1; i<=n; i++)//对于每一个点
		for (int j=0; j<f[i].size(); j++)//这个是针对每一条出边,f,g无所谓
		{
			int u=f[i][j].v,p=f[i][j].w,q=g[i][j].w,r=2;//u是抵达点,p是第一个导航的抵达点,q是第二个导航的抵达点
			if (dis1[u]-dis1[i]==p) r--;//发现是在第一个导航最短路上,然后警告数-1
			if (dis2[u]-dis2[i]==q) r--;//发现是在第二个导航最短路上,然后警告数-1
			ans[u].push_back({i,r});//存储边和权值
		}
	spfa(ans,dis3,1);
	printf("%d
",dis3[n]);
}
int main()
{
	init();
	return 0;
}