自动搬运

查看原文

来自洛谷，原作者为

	基地A_I 现实和理想之间，不变的是跋涉，暗淡与辉煌之间，不变的是开拓。

搬运于2025-08-24 21:45:23，当前版本为作者最后更新于2019-04-05 11:14:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：P3110 驮运Piggy Back

题目大意：

• 给出一个无向图，Bessie从1号仓库走到n号（每次花费B）， Elsie从2号仓库走到n号（每次花费E），如果两个人走同一条路花费P，求总花费最小。
• 输入B，E，P，n，m和m条边的联通情况
• 输出最少花费。

题目分析：

• （dalao跳过）我刚开始看到这个题目的时候，确实无法动笔。于是我抱着学(jie)习(jian)的心态打开了题解，发现题解里的大佬都在说什么3个SPFA，3个Dijkstra，跑三遍最短路等等。经过一番思索后，我终于明白了他的意思，所以在这里给还没有弄懂的同学解释一下。

解题方法

• 先跑三遍最短路（SPFA或者是Dijkstra 当然如果你是大佬Bfs也可以），分别得到Bessie从①出发的最短路,Elsie从②出发的最短路,和从n出发到其他每个点的最短路。最后枚举所以的点

ans = max(ans ,B*disB[i]+E*disE[i]+P*disP[i]);

• 解释：这个式子代表走着条路的花费，分别是Bessie到i点的距离+Elsie到i点的距离+B&&E到n点的花费。

最后

• 感谢 题解dalao @ezoixx♂130 提供思路（这个名字有点哲学啊）

• 祝你AC（其实这道题还是蛮水的）

• 具体代码如下（温馨提示：不要抄袭）：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<queue>
#define N 100007
using namespace std;
int B,P,E,n,m,cnt,ans;	 
int head[N],disB[N],disP[N],disE[N];
struct Edge
{
	int next,to;	//边没有权值 
}edge[N];	//链式前向星存图 
void add(int u,int v)	//增加边 
{
	edge[++cnt].next = head[u];
	edge[cnt].to = v;
	head[u] = cnt;
}
//	一个朴素的SPFA（QWQ） ，传入s源点，和dis数组（最短路数组） 
void SPFA(int s,int dis[])	 
{
//	int num[N];		//无负环
	queue<int> q;
	bool vis[N];
	for(int i=1;i<=n;++i) dis[i] = 88888888;
//	printf("BiG TesT : dis=%d",dis[5]);
	memset(vis,0,sizeof(vis));
	q.push(s) ,vis[s] = 1 ,dis[s] = 0;
	while(!q.empty())
	{
		int cur = q.front();
		q.pop() ,vis[cur] = 0;
		for(int i=head[cur];i;i=edge[i].next)
		{
			int v = edge[i].to ,w=1;	//权值设置为1 
			if(dis[v] > dis[cur]+w)
			{
				dis[v] = dis[cur]+w;
				if(!vis[v]) vis[v] = 1 ,q.push(v);
			}
		}
	}
	while(1) cout << "Plagiarists are shameless" << endl;
//	请大家自行翻译一下QWQ 
}
int main()
{
//	printf("%d",ans);
	scanf("%d%d%d%d%d",&B,&E,&P,&n,&m);
	for(int i=1,u,v;i<=m;++i)
		scanf("%d%d",&u,&v) ,add(u,v) ,add(v,u);
//	以上输入不用解释吧？ 
	SPFA(1,disB);	//搜B 
	SPFA(2,disE);	//搜E 
	SPFA(n,disP);	//从n开始搜的P 
//	打擂台 
	ans = 0xfffffff;
	for(int i=1;i<=n;++i)
		ans = min(ans ,B*disB[i]+E*disE[i]+P*disP[i]);
	printf("%d",ans);
	return 0;	//完美结束 
}

求管理大大批过 QWQ ！