Submission

[PP-SSSSSSSSSSSSSSSSS]

Score: 0

User: hmmm

Problemset: C.Love Sick

Language: cpp

Time: 0.003 second

Submitted On: 2025-01-09 19:55:11

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int N=1005,M=15,K=1e9;
int dis[M][N];
bool inq[M][N];
vector<pii> g[N];

int main(){
//	ios::sync_with_stdio(0); cin.tie(0);
	int n,m,k;
	cin >> n >> m >> k;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	int l=0,r=1e9;
	while(l<r){
		int mid=(l+r)/2;
		queue<pii> q;
		while(!q.empty()) q.pop();
		for(int i=0;i<=k;i++){
			for(int j=0;j<=n;j++){
				dis[i][j]=K;
				inq[i][j]=false;
			}
		}
//		cout << mid << "\n";
		bool chk=false;
		q.push({0,0});
		dis[0][0]=0;
		int cnt=0;
		while(!q.empty()){
			auto st=q.front().first;
			auto x=q.front().second;
			q.pop();
			inq[st][x]=false;
			if(x==n-1){
				chk=true;
				break;
			}
//			cnt++;
//			cout << dis[st][x] << ' ' << st << ' ' << x << "--\n";
			for(auto e:g[x]){
				auto xx=e.first;
				auto w=e.second;
//				cout << x << ' ' << w << "\n";
				if(dis[st][x]+w<mid && dis[st][x]+w<dis[st][xx]){
					dis[st][xx]=dis[st][x]+w;
					if(!inq[st][xx]){
						inq[st][xx]=true;
						q.push({st,xx});
//						cout << dis[st][xx] << ' ' << st << ' ' << xx << "aa\n";
					}
				}
				if(st+1<=k){
					if(dis[st][x]-w<dis[st+1][xx]){
						dis[st+1][xx]=dis[st][x]-w;
						if(!inq[st+1][xx]){
							inq[st+1][xx]=true;
							q.push({st+1,xx});
//							cout << dis[st+1][xx] << ' ' << st+1 << ' ' << xx << "bb\n";
						}
					}					
				}
			}
		}
		if(chk) r=mid;
		else l=mid+1;
	}
	cout << l;
}