P9504 题解（2023 激励计划评分 7）
WsW_
·
·
题解
更新：
这是一篇已通过的题解。
感谢指出问题
总思路
要我们开始就确定一个 k 很难，但根据题目要求，到达终点时 k=0。
而此题中是无向图，因此我们反着跑。一开始 k=0，每走一步 k\gets k+1，从终点跑去起点即可。
后面的思路都是直接按反走说的，即后文“终点”为题目“起点”。
一、直接反跑单源最短路
套上 dijkstra 板子，发现此题多了一个量 k，怎么办？
在 dist 数组中新增一维，对于 dist_{i,j} 意为：k=i，到点 j 时所需的最小生命值。
其他同 dijkstra 板子。
---
#### 代码与[提交记录](https://www.luogu.com.cn/record/119347691)
```cpp
#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$ 分。
---
### 代码与[提交记录](https://www.luogu.com.cn/record/119366774)
```cpp
#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;
}
```