如题

由于AFO已久，部分写法可能不规范，轻喷

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 20010;
const int W = 110;
struct Edge { int to, w; };
int n, m, s, t;
vector<Edge> to[N * W];
int dist[N * W], vis[N * W];
priority_queue<PII, vector<PII>, greater<PII>> q;
int layer(int p, int l) { return p + n * (l - 1); }
int getl(int p) { if(p % n == 0) return p / n; return p / n + 1; }
int main() {
	memset(dist, 0x3f, sizeof dist);
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for(int i = 1; i <= m; i ++ ) {
		int u = 0, v = 0, w = 0;
		scanf("%d%d%d", &u, &v, &w);
		for(int j = 1; j <= 101; j ++ ) {
			to[layer(u, j)].push_back({layer(v, j + 1), w});
			to[layer(v, j)].push_back({layer(u, j + 1), w});
		}
	}
	dist[t] = 0;
	q.push({0, t});
	while(!q.empty()) {
		PII tp = q.top(); q.pop();
		int u = tp.second, d = tp.first;
		if(vis[u]) continue;
		vis[u] = 1;
		for(unsigned i = 0; i < to[u].size(); i ++ ) {
			int v = to[u][i].to, w = to[u][i].w;
			if(d + w / getl(u) > dist[v]) continue;
			dist[v] = d + w / getl(u);
			q.push({d + w / getl(u), v});
		}
	}
	int ans = 0x3f3f3f3f;
	for(int i = 1; i <= 101; i ++ ) ans = min(ans, dist[layer(s, i)]);
	printf("%d\n", ans);	
	return 0;
}