#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) x&-x
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10;
const int M=2e6+10;
struct node{
	int v,w,k;
};
vector<node>g[N];
int n,m,x,y;
struct cmp{
	bool operator()(pair<int,int>u,pair<int,int>v){
		return u.second>v.second;
	}
};
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>q;
int dis[N];
bool vis[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m>>x>>y;
	for(int i=1;i<=m;i++){
		int u,v,w,k;
		cin>>u>>v>>w>>k;
		g[u].push_back({v,w,k});
		g[v].push_back({u,w,k});
	}
	memset(dis,0x3f,sizeof(dis));
	q.push({x,0});
	dis[x]=0;
	while(!q.empty()){
		int u=q.top().first;
		q.pop();
		if(vis[u])	continue;
		vis[u]=1;
		for(auto p:g[u]){
			int v=p.v;
			int w=p.w;
			int k=p.k;
			int cnt=dis[u];
			if(cnt%k)	cnt=(dis[u]/k)*k+k;
			cnt+=w;
			if(dis[v]>cnt){
				dis[v]=cnt;
				q.push({v,cnt});
			}
		}
	}
	if(dis[y]==INF){
		cout<<-1;
		return 0;
	}
	cout<<dis[y];
    return 0;
}

如果去掉题目中的 $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;
}