用链式前向星 + 反向BFS写的

#include<bits/stdc++.h>
using namespace std;
struct LM	//little M
{
	int i,life,magic;
};
struct Edge
{
	int to,next,w;
}edge[400005];
int tot=0,head[40005];
int ans=999999999,vis[400005];
void Add(int from,int to,int w)
{
	edge[++tot].to=to;
	edge[tot].w=w;
	edge[tot].next=head[from];
	head[from]=tot;
}
void BFS(int s,int t)
{
	queue<LM> a;
	a.push(LM{s,0,0});
	while(a.size())
	{
		LM u=a.front();
		a.pop();
		
		if(u.i==t)
		{
			ans=min(ans,u.life);
		}
		
		for(int i=head[u.i];i!=-1;i=edge[i].next)
		{
			if(u.life+edge[i].w/(u.magic+1)<vis[edge[i].to])
			{
				a.push(LM{edge[i].to,u.life+edge[i].w/(u.magic+1),u.magic+1});
				vis[edge[i].to]=u.life+edge[i].w/(u.magic+1);
			}
		}
	}
}
int main()
{
	int n,m,s,t;
	cin>>n>>m>>s>>t;
	fill(head,head+40005,-1);
	fill(vis,vis+400005,999999999);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		Add(u,v,w);
		Add(v,u,w);
	}
	
	vis[t]=0;
	BFS(t,s);
	cout<<ans;
	return 0;
}