自动搬运

查看原文

来自洛谷，原作者为

	licn 天生我材必有用，千金散尽还复来。

搬运于2025-08-24 21:35:48，当前版本为作者最后更新于2023-08-23 21:56:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析：

本题是在最短路的基础上多维护了一个路径，我们正常去做最短路。

做法：

用 spfa 去跑最短路，由于需要维护最少丢失率，我们可以维护最大剩余率，最后用 $1$ 减，可以保证精度。当丢失率相等时再去判断一下延时长短。

切记：丢失率可能是 $0$ 存图的时候注意不要特判是 $0$ 时不存。（本人栽了）

spfa：当一个点的最优值被更新时，那么需要更新与它相连的点。如果需要去更新的点已在队列里不必再入队。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=310;
const double eps=1e-6;
int n,l,r,t[N][N],head[N],tot;
double loss[N][N];
struct node
{
	int next,to,dis2;
	double dis1;//dis1[]剩余率，dis2[]延时
}edge[N*N];
void read(int from,int to,double dis1,int dis2)
{
	tot++;
	edge[tot].to=to;
	edge[tot].dis1=dis1;
	edge[tot].dis2=dis2;
	edge[tot].next=head[from];
	head[from]=tot;
}
void spfa()
{
	double ans1[N]={0};//剩余率
	int ans2[N]={0},v[N]={0};//ans2[]延时，v[]标记是否在队列里
	ans1[l]=1,v[l]=1;
	queue<int>q;
	q.push(l);
	while(q.size())
	{
		int x=q.front();
		q.pop();
		v[x]=0;
		for(int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to;
			if(ans1[x]*edge[i].dis1>ans1[y])
			{
				ans1[y]=ans1[x]*edge[i].dis1;
				ans2[y]=ans2[x]+edge[i].dis2;
				if(v[y]==0)q.push(y),v[y]=1; //如果已经在队列里不必再次入队
			}
		}
	}
	printf("%d %.4lf",ans2[r],1-ans1[r]);
}
int main(){
	scanf("%d%d%d",&n,&l,&r);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&t[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%lf",&loss[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(t[i][j]!=-1&&loss[i][j]!=-1)
				read(i,j,1-loss[i][j],t[i][j]),read(j,i,1-loss[i][j],t[i][j]);
	spfa();
	return 0;
}