题解 | #武#

#include <bits/stdc++.h>

using namespace std;

int n,p,k;

const int maxn=200005;

const int inf=0x3f3f3f3f;

struct node { int v; int w; node(int v,int w):v(v),w(w){} bool operator<(const node & t)const { return w>t.w; } };

vectordij[maxn];

int vis[maxn];

int dis[maxn];

void dijkstra(int s) { memset(vis,0,sizeof(vis));

memset(dis,inf,sizeof(dis));

dis[p]=0;

priority_queue<node> Q;

Q.push(node(s,dis[s]));
	
while(!Q.empty())
{
    int u=Q.top().v;  //点 
    Q.pop();
    if(vis[u])
    continue;

    vis[u]=1;

    for(int i=0;i<dij[u].size();i++)
    {
        int v=dij[u][i].v;
        int w=dij[u][i].w;
        if(dis[v]>dis[u]+w)
        {
            dis[v]=dis[u]+w;
            Q.push(node(v,dis[v]));
        }
    }
}

} int main() { cin>>n>>p>>k; for(int i=0;i<n-1;i++) { int u,v,w; cin>>u>>v>>w; dij[u].push_back(node(v,w)); dij[v].push_back(node(u,w)); }

dijkstra(p);
sort(dis+1,dis+1+n);
cout<<dis[k+1];
return 0;

}