自动搬运

查看原文

来自洛谷，原作者为

	WsW_ 欢迎入群872763867||题解求赞！题解看不懂请私信

搬运于2025-08-24 22:49:00，当前版本为作者最后更新于2023-08-06 18:40:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

更新：

这是一篇已通过的题解。

• $2023.08.06$ 全角空格改半角空格，顺手改了几个标点，完善了一些说明。
• $2023.11.25$ 补上缺失的空格。

感谢指出问题

总思路

要我们开始就确定一个 $k$ 很难，但根据题目要求，到达终点时 $k=0$。
而此题中是无向图，因此我们反着跑。一开始 $k=0$，每走一步 $k\gets k+1$，从终点跑去起点即可。
后面的思路都是直接按反走说的，即后文“终点”为题目“起点”。

一、直接反跑单源最短路

套上 dijkstra 板子，发现此题多了一个量 $k$，怎么办？
在 $dist$ 数组中新增一维，对于 $dist_{i,j}$ 意为：$k=i$，到点 $j$ 时所需的最小生命值。 其他同 dijkstra 板子。

$38$ 分，后两个 subtask 空间炸了。

代码与提交记录

#include<bits/stdc++.h>
using namespace std;

struct node{
	int val,next,to;
}edg[80005];
int elen;
struct point{
	int ans,cnt,x;
	bool operator < (const point &A)const{
		return ans>A.ans;
	}
};

priority_queue<point> q;

int x,y,z;
int n,m,s,t;
int ans[20003][20003];//此为dist数组
int head[20003];
int fans;

void add(int u,int v,int val){
	elen++;
	edg[elen].to=v;
	edg[elen].val=val;
	edg[elen].next=head[u];
	head[u]=elen;
	
}

signed main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			ans[i][j]=1e9;
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	swap(s,t);
	ans[1][s]=0;
	q.push({0,1,s});
	while(!q.empty()){
		point xx=q.top();
		q.pop();
		y=xx.cnt;
		x=xx.x;
		for(int i=head[x];i;i=edg[i].next){
			int to=edg[i].to;
			int cost=edg[i].val;
			if(ans[y+1][to]>ans[y][x]+cost/y){
				ans[y+1][to]=ans[y][x]+cost/y;
				q.push({ans[y+1][to],y+1,to});
			}
		}
	}
	fans=1e9;
	for(int i=1;i<=n;i++)fans=min(fans,ans[i][t]);
	printf("%d",fans);
	return 0;
}

二、剪枝

由于前面是空间炸了，说明正确性是没问题的，接着优化空间。
看了下数据范围，发现 $0\le w\le 100$，不禁想起某次模拟赛的第一题的思路：当达到某个状态时，后续无论怎样变化，答案不会改变。

本题中扣血的方法是：扣 $\left\lfloor\dfrac{w}{k}\right\rfloor$ 的血量，因此当 $k>w$ 时不会扣血。而数据范围 $w\le 100$，所以当 $k>100$ 时，后面无论怎样走都不会扣血。
题目中保证是连通图，所以 $k>100$ 时我们可以从当前位置无伤走到终点。
我们记录答案的 $dist$ 数组第一维就只用开到 $100$，当然数组要稍微开大点。
跑最短路的时候如果 $k>100$，那直接记录答案，跳过后续操作即可。

$100$ 分。

代码与提交记录

#include<bits/stdc++.h>
using namespace std;

struct node{
	int val,next,to;
}edg[80005];
int elen;
struct point{
	int cnt,x;
};
queue<point> q;

int x,y,z;
int n,m,s,t;
bool vis[103][20003];
int ans[103][20003];//此为dist数组
int head[20003];
int fans=1e9;

void add(int u,int v,int val){
	elen++;
	edg[elen].to=v;
	edg[elen].val=val;
	edg[elen].next=head[u];
	head[u]=elen;
	
}

signed main(){
 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
 	cin>>n>>m>>s>>t;
	for(int i=1;i<=101;i++){
		for(int j=1;j<=n;j++){
			ans[i][j]=1e9;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	swap(s,t);
	ans[1][s]=0;
	q.push({1,s});
	while(!q.empty()){
		point xx=q.front();
		q.pop();
		y=xx.cnt;
		x=xx.x;
		vis[y][x]=0;
		if(y>100){
			fans=min(fans,ans[y][x]);
			continue;
		}
		for(int i=head[x];i;i=edg[i].next){
			int to=edg[i].to;
			int cost=edg[i].val;
			if(ans[y+1][to]>ans[y][x]+cost/y){
				ans[y+1][to]=ans[y][x]+cost/y;
				if(!vis[y+1][to]){
					q.push({y+1,to});
					vis[y+1][to]=1;
				}
			}
		}
	}
	for(int i=1;i<=101;i++)fans=min(fans,ans[i][t]);
	cout<<fans;
	return 0;
}