自动搬运

查看原文

来自洛谷，原作者为

	Clare613 csacademy.com||宣:https://www.luogu.com.cn/team/103922||250粉后橙名就别找我了||目标一：黄+绿+蓝+紫+黑->431/888||目标二：2025J：320+，2025S:250+||个人题库已满

搬运于2025-08-24 21:44:54，当前版本为作者最后更新于2024-08-05 10:46:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

建议降黄或橙 or 加强数据

题目大意:

就是让 $L+X/C$ 小就行了。

思路：

最容易想到的是 SPFA ，但因数据较小，所以 DFS 也能过，而我们的 DFS 是来找容量和延迟最小的最大值。

code

#include<bits/stdc++.h>
using namespace std;
struct node{
	int v,w,fj;
};
vector<node> a[505];
int cnt[505],sum,l[505],ctn,minn=1e9;
int n,m,qwe;
bool f[505][505];
void dfs(int sum,int maxn,int now){//dfs
	if(sum+maxn>minn) return ;//剪枝
	if(now==n){
		minn=min(minn,sum+maxn);//求最小值
		return ;
	}
	for(int i=0;i<a[now].size();i++){
		if(f[now][a[now][i].v]) continue;//走过就不能走
		f[now][a[now][i].v]=1;//标记
		dfs(sum+a[now][i].w,max(maxn,a[now][i].fj),a[now][i].v);//转移
		f[now][a[now][i].v]=0;//取消标记
	}
}
int main(){
	cin>>n>>m>>qwe;
	for(int i=1;i<=m;i++){
		int x,y,z,q;
		cin>>x>>y>>z>>q;
		//建边
		a[x].push_back({y,z,floor(qwe/q)});
		a[y].push_back({x,z,floor(qwe/q)});
	}
	dfs(0,0,1);
	cout<<minn;//输出
	return 0;
}