这题我们发现如果直接去枚举生命和法力值显然是不行的，又看到说最小的生命值，不禁想到最短路，但是怎么跑？
我们令经过一条边之前魔力值为 \(k\)，那么该边的边权为 \(\lfloor\dfrac{w}{k}\rfloor\)，于是我们讲题目转化为了边权为 \(\lfloor\dfrac{w}{k}\rfloor\) 时 \(s\) 到 \(t\) 的最短路径。
我们不知道最短路径一共要经过多少条边，也就无法知道初始魔力值究竟有多少。那我们不妨反着想，考虑从 \(t\) 到 \(s\) 的最短路径，这时我们就不用知道初始魔力值是多少，而是每经过一个边，就将 \(k\leftarrow k+1\)。
但是此时仍无法直接跑最短路，因为每一次不同时刻经过一条边，他的边权都是不一样的。此时数据范围 \(w\leq 100\) 很好的提示了我们。
妈妈，我会拆点分层图！
我们将原本的一个点拆成 \(100\) 个点，因为 \(w\) 最大为 \(100\)，若经过的边数（即魔力值）\(k>100\)，那么他的边权 \(w\) 就必然为 \(0\)，我们就不需要考虑了，因为不会对我们的答案产生影响。
于是对于点 \(x\)，我们将其拆成 \(100\) 个点 \(x\times 100+i(1\leq i\leq 100)\)，其中的 \(i\) 表示在 \(x\times 100+i\) 这个点时的魔力值为 \(i\)，于是显然的对于两个点 \(u,v\)，其边权为 \(w\)，若其在原始图上有边相连，那么我们就在分层图上将 \(u\times 100 +i(1\leq i < 100)\) 与 \(v\times 100 +i+1\) 相连，其边权为 \(\lfloor\dfrac{w}{i}\rfloor\)。
最后也就很简单了，我们在新的分层图上跑一遍 \(t\)（新图上为 \(t\times 100 +1\)） 到 \(s\) 的最短路，最后在 \(s\) 点的所有层里面找最小值即为最终答案。
#include<bits/stdc++.h>
using namespace std;
const int NR=3e6;
const int MX=2e4;
int n,m,s,t;
vector<int>e[NR],g[NR];
void add(int u,int v,int w){
e[u].push_back(v),g[u].push_back(w);
}
bool vis[NR];
int dis[NR],ans;
queue<int>q;
void spfa(int _s){
memset(vis,false,sizeof(vis));
memset(dis,0x3f3f3f3f,sizeof(dis));
ans=dis[0];
q.push(_s),vis[_s]=true,dis[_s]=0;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=false;
for(int i=0;i<e[u].size();++i){
int v=e[u][i],w=g[u][i];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v])q.push(v),vis[v]=true;
}
}
}
}
int main(){
cin>>n>>m>>s>>t;
for(int i=1,u,v,w;i<=m;++i){
cin>>u>>v>>w;
for(int j=1;j<100;++j){
add(u*100+j,v*100+j+1,w/j);
add(v*100+j,u*100+j+1,w/j);
}
}
spfa(t*100+1);
for(int i=s*100+1;i<=s*100+100;++i)
ans=min(ans,dis[i]);
cout<<ans<<endl;
return 0;
}