有dalao康康啥情况嘛

萌新堆优化Dijkstra WA了一个点 #7

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 10;
const int inf = 0x3f3f3f3f;
typedef pair<long long ,long long > PII;
priority_queue<PII,vector<PII>,greater<PII> > q;
long long e[maxn],w[maxn],ne[maxn],h[maxn],idx;
long long dis[maxn];
bool vis[maxn];
long long n,m,k;
void init(){
	memset(h,-1,sizeof(h));
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
}
void add(long long a,long long b,long long v){
	e[idx] = b;
	w[idx] = v;
	ne[idx] = h[a];
	h[a] = idx++;
}
long long dijkstra(long long mid){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[1] = 0;
	q.push(make_pair(0,1));
	while(!q.empty()){
	    long long u = q.top().second;
	    q.pop();
		if(vis[u]) continue;
		else vis[u] = true;
		for(long long i = h[u];~i;i = ne[i]){
			long long v = e[i];
			long long distance = w[i];
			if(distance > mid) distance = 1;
			else distance = 0;
			
			if(dis[v] > distance + dis[u]){
				dis[v] = distance + dis[u];
				q.push(make_pair(dis[v],v));
			}
		}
	}
	return dis[n];
}
int main(){
	init();
	long long bound = -inf,ans = 0;
	cin>>n>>m>>k;
	while(m--){
		long long a,b,v;
		cin>>a>>b>>v;
		add(a,b,v);
		add(b,a,v);
		bound = max(bound,v);
	}
	if(dijkstra(0) == inf) cout<<-1;
	else{
		long long l = 0,r = bound;
		long long mid;
		while(l <= r){
			mid = (l + r) / 2;
			if(dijkstra(mid) <= k){
				ans = mid;
				r = mid - 1;
			}else l = mid + 1;
		}
		cout<<ans;
	}
	return 0;
}