如果去掉题目中的 $K$ ，这就是一道模板最短路。不过加上也很简单，只不过是计算略有变化而已。

我们容易发现：从 $u$ 到 $v$ 的 $dis[v]$ 其实就是大于等于 $dis[u]$ 的最小 $k$ 的倍数加上 $w$ 。其中，$u, v, k, w$ 题目都已给出，而 $dis$ 就是到当前点的最短时间而已。

形式地说，设 $f(w, k)$ 表示大于等于 $w$ 的最小 $k$ 的倍数，那么 $dis[v] = min(dis[v], f(dis[u], k) + w)$

（另外地说，本题中认为 $0$ 是所有数的倍数）

代码

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

int T = 1;
const int N = 2e5 + 10;
const int INF = 1e16;
int n, m, x, y;

int head[N], nx[N], to[N], wei[N], tk[N], cnt;
void AddEdge(int u, int v, int w, int k) {
	nx[++cnt] = head[u];
	to[cnt] = v;
	wei[cnt] = w;
	tk[cnt] = k;
	head[u] = cnt;
}

struct Cmp {//pair<u，w>
	bool operator() (const pair<int, int>& a, const pair<int, int>& b) const {
		return a.second > b.second;
	}
};

int WorkOut(int res, int k) {//计算大于等于res的最小k的倍数
	int t = res / k, ans = -1;
	if (res % k == 0) {
		ans = t * k;
	} else ans = (t + 1) * k;
	return ans;
}

int dis[N];
bool vis[N];
void Dijkstra() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> heap;
	fill(dis, dis + 1 + n, INF);
	dis[x] = 0;
	heap.push({x, 0});
	while (!heap.empty()) {
		int u = heap.top().first;
		heap.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int ei = head[u]; ei != 0; ei = nx[ei]) {
			int v = to[ei], w = wei[ei], k = tk[ei];
			int nw = WorkOut(dis[u], k);
			if (nw + w < dis[v]) {
				dis[v] = nw + w;
				heap.push({v, dis[v]});
			}
		}
	}
	cout << (dis[y] == INF ? -1 : dis[y]);
}

void Solve() {
	cin >> n >> m >> x >> y;
	for (int i = 1; i <= m; i++) {
		int u, v, w, k;
		cin >> u >> v >> w >> k;
		AddEdge(u, v, w, k);
		AddEdge(v, u, w, k);
	}
	Dijkstra();
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	while (T--) {
		Solve();
	}
	return 0;
}