Submission

[PPTSSSSSSSSSSSSSSSSS]

Score: 0

User: hmmm

Problemset: C.Love Sick

Language: cpp

Time: 1.060 second

Submitted On: 2025-01-05 15:39:12

#include<bits/stdc++.h>
using namespace std;
using pii=array<int,3>;
const int N=1e3+5;
vector<pair<int,int>> g[N]; 
int dis[13][N];
bool vis[13][N];
int n,m,k;

inline bool think(int mid){
//	priority_queue<pii> q;
	priority_queue<pii,vector<pii>,greater<pii>> q;
	memset(dis,0x3f,sizeof dis);
//	 memset(vis,false,sizeof vis);
	q.push({dis[0][0]=0,0,0});
//	cout << mid << "  ---\n";
	while(!q.empty()){
		auto l=q.top()[0];
		auto x=q.top()[1];
		auto st=q.top()[2];
		q.pop();
//		cout << l << ' ' << x << ' ' << st << "\n";
//		if(vis[st][x]) continue;
//		vis[st][x]=true;
		if(x==n-1) return true;
		for(auto e:g[x]){
			auto xx=e.first;
			auto ll=e.second;
//			cout << xx << ' ' << ll << "\n";
			if(st+1<=k){
//				cout << "a" << "\n";
				if(dis[st+1][xx]>dis[st][x]-ll){
					dis[st+1][xx]=dis[st][x]-ll;
					q.push({dis[st+1][xx],xx,st+1});
//					cout << "aa\n";
				}
			}
			if(l+ll<mid){
//				cout << "b\n";
				if(dis[st][xx]>dis[st][x]+ll){
					dis[st][xx]=dis[st][x]+ll;
					q.push({dis[st][xx],xx,st});
//					cout << "bb\n";					
				}
			}
		}	
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	int l=0,r=11e8;
	for(int i=1;i<=n;i++){
		int u,w,v;
		cin >> u >> v >> w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
//		l=min(l,w);
		// r+=w;
	}
	int ans=0;
	while(l<r){
		int mid=(l+r)/2;
		bool chk=think(mid);
//		cout << mid << ' ' << chk << "\n";
		if(chk!=true) l=mid+1;
		else r=mid;
		if(chk) ans=mid;
	}
	cout << ans;
}