块级代码隐藏代码:c++/python

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;

#define N 50010
#define inf 0x7f7f7f7f

struct node {
    int u,dis;
    node () {};
    node (int D,int U) { u=U; dis=D; }
    bool operator < (const node& h) const {
		return dis>h.dis;
	}
};

struct Gragh {
    int v,w;
    Gragh () {};
    Gragh (int V,int W) {v=V;w=W;}
};

int P[10],n,m,k,ans=inf,vis[N],sum=1,dis[N];
vector<Gragh> G[N];
priority_queue<node> q;

int dijkstra(int st,int P) {
    q.push( node (0,st) );
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    memset(vis,0,sizeof(vis));
    while(!q.empty() ) {
        node now=q.top();
        q.pop();
        if(vis[now.u]) continue;
        vis[now.u]=1;
        for(int i=0,v,w,w1;i<G[now.u].size();i++) {
            v=G[now.u][i].v,w=G[now.u][i].w;
            if(w>=P) w1=1;
            else w1=0;
            if(dis[now.u]+w1<dis[v]) {
                dis[v]=dis[now.u]+w1;
                q.push( node (dis[v],v));
            }
        }
    }
    return dis[n];
}

bool check(int mid) {
    if(dijkstra(1,mid)<=k) return 1;
    return 0;
}

/*
4 3 3
1 2 1
2 3 2
3 4 3
*/

int main() {
    int maxw=0;
    cin>>n>>m>>k;
    for(int i=1,u,v,w;i<=m;i++) {
        cin>>u>>v>>w;
        maxw=max(maxw,w);
        G[u].push_back( Gragh(v,w) );
        G[v].push_back( Gragh(u,w) );
    }
    int mid,l=0,r=maxw,flag=0;
    while(l<r) {
        mid=(l+r+1)/2;
        if(check(mid)) r=mid-1,flag=1;
        else l=mid;
    }
    if(!flag) cout<<"-1";
    else cout<<l;
}