自动搬运

查看原文

来自洛谷，原作者为

	Reywmp 晦

搬运于2025-08-24 21:45:22，当前版本为作者最后更新于2018-10-20 15:34:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

2018.11.18 才发现venus大佬的评论，修改一个小错误 2018.10.2 修改部分解释，添加代码注释

貌似没有人用Dijkstra写呢。

其实这一题可以用Dij写的。思路其实很简单

我们可以写一个标准的dij模板，然后一共跑3遍。

分别是分3次重新构建图：

1.我们将GPS1的图存入邻接表。跑一遍dij

2.然后我们将GPS2的图再存入邻接表。再跑一遍dij

3.最后我们将2次跑过的dij,得到的最短路后所发出的警告数(分别不在2个Gps的次数)上当成边权。再跑一遍dij。

简单来说是3*汇点->源点某大佬指教的说法

每次要用不同的数组存。

最后输出dis3[1]最小警告数即可

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#define N 10005
#define M 50005
using namespace std;
void fastin(int &a){
	char c=getchar();
	a=0;
	while((c<'0'||c>'9')&&c!='-'){	c=getchar();}
	int f=1;
	if(c=='-'){f=-1;c=getchar();}
	while(c>='0'&&c<='9'){	a=(a<<1)+(a<<3)+c-48;c=getchar();}
	a*=f;
}
int n,m;
int cnt=0;
struct Node
{
	int from,to,VA1,VA2;
}E[M];
struct Rey
{
	int nxt,to,VA;
}e[M];
int ds1[N];
int ds2[N];
int ds3[N];
struct pq
{
	int to,VA;
	bool operator < (const pq &x)const{
		return VA>x.VA;//re define 
	}//dij需要使用堆，优先队列重定向。
};
int head[N];
int vis[N];
priority_queue<pq>q;
void ADDside(int u,int v,int w)
{
	++cnt;
	e[cnt].nxt=head[u];
	e[cnt].VA=w;
	e[cnt].to=v;
	head[u]=cnt;
}
void Dijkstra(int u,int *ds)
{
	pq now;
	for(int i=1;i<=n;i++)
	{
		ds[i]=1<<30;
		vis[i]=0;//初始化
	}
	now.to=u;
	now.VA=ds[u]=0;
	q.push(now);
	while(!q.empty())
	{
		u=q.top().to;
		q.pop();
		if(vis[u])continue;//访问过了跳过
		vis[u]=1;
		for(register int i=head[u];i!=0;i=e[i].nxt)
		{
			int v=e[i].to;
			int xl=ds[u]+e[i].VA;
			if(vis[v]==0&&xl<ds[v])
			{
				ds[v]=xl;
				now.to=v;
				now.VA=ds[v];
				q.push(now);//更新
			}
		}
	}
}//标准dij
int main()
{
	//freopen("gpsduel.in","r",stdin);
	//freopen("gpsduel.out","w",stdout);
	fastin(n);
	fastin(m);
	for(register int i=1;i<=m;i++)
	{
		fastin(E[i].to);
		fastin(E[i].from);
		fastin(E[i].VA1);
		fastin(E[i].VA2);
	}
	memset(head,0,sizeof(head));
	memset(e,0,sizeof(e));
	cnt=0;//每次都要先初始化edge，head数组，cnt也要清理，因为要重存图
	for(register int i=1;i<=m;i++)
	{
		ADDside(E[i].from,E[i].to,E[i].VA1);//存图
	}
	Dijkstra(n,ds1);
	memset(head,0,sizeof(head));
	memset(e,0,sizeof(e));
	cnt=0;
	for(register int i=1;i<=m;i++)
	{
		ADDside(E[i].from,E[i].to,E[i].VA2);//1次重构
	}
	Dijkstra(n,ds2);
	memset(head,0,sizeof(head));
	memset(e,0,sizeof(e));
	cnt=0;
	for(register int i=1;i<=m;i++)
	{
		int sum=0;
		if(ds1[E[i].to]!=ds1[E[i].from]+E[i].VA1)
		sum++;
		if(ds2[E[i].to]!=ds2[E[i].from]+E[i].VA2)
		sum++;
		ADDside(E[i].from,E[i].to,sum); //2次重存
	}
	Dijkstra(n,ds3);
	printf("%d",ds3[1]);//最少的警告数
	putchar('\n');
	return 0;
}