Submission

[P-SSSSSSSSSSSSSSSSSS]

Score: 0

User: mydKN

Problemset: C.Love Sick

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-27 09:15:47

#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

struct stc{
	int w, t, u;
	bool operator<(const stc& a) const{
		if(w != a.w) return w > a.w;
		return t > a.t;
	}
};

const int maxn = 1e3 + 10;
const int maxk = 15;
const int inf = 2e9;

int n, m, k;
vector<pii> adj[maxn];
int dist[maxn][maxk];
priority_queue<stc> pq;
bool visited[maxn][maxk];
int res = inf;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> k;
	for(int i=0;i<m;++i){
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].emplace_back(w, v);
		adj[v].emplace_back(w, u);
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<=k;++j){
			dist[i][j] = inf;
		}
	}
	dist[0][0] = 0;
	pq.push({0, 0, 0});
	while(!pq.empty()){
		auto [w, ut, u] = pq.top();
		pq.pop();
		if(visited[u][ut]) continue;
		visited[u][ut] = 1;
		for(auto [vw, v] : adj[u]){
			if(ut < k && dist[v][ut + 1] > dist[u][ut] - vw && !visited[v][ut + 1]){
				dist[v][ut + 1] = dist[u][ut] - vw;
				pq.push({dist[v][ut + 1], ut + 1, v});
			}
			if(dist[v][ut] > dist[u][ut] + vw && !visited[v][ut]){
				dist[v][ut] = dist[u][ut] + vw;
				pq.push({dist[v][ut], ut, v});
			}
		}
	}
	for(int i=0;i<=k;++i){
		res = min(res, dist[n-1][i]);
	}
	cout << res;
}