武

题目链接：https://ac.nowcoder.com/acm/problem/15522

就是一道很常规的dijskstra题，虽然我自己debug 疯了（丢脸>_<)

#include<bits/stdc++.h>
using namespace std;

const int N=2e6+10;
int n,p,k;
int q[N],tt=-1,hh;
bool st[N];
int e[N],ne[N],idx,w[N],h[N];
int u,v,l;
int dist[N];

void add(int u,int v,int l)
{
    e[idx]=v;
    w[idx]=l;
    ne[idx]=h[u];
    h[u]=idx++;
}

void dijkstra()
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    //st[p]=1;//这里我之前以为也要处理，结果就WA了，可以看后面，如果这里将p处理了，那么后面就直接continue;
    q[++tt]=p;
    dist[p]=0;
    while(tt>=hh)
    {
        int x=q[hh++];
        if(st[x])continue;
        st[x]=1;
        for(int i=h[x];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[x]+w[i])
            {
                dist[j]=dist[x]+w[i];
                q[++tt]=j;
            }
        }
    }
}
int main()
{
    cin>>n>>p>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        cin>>u>>v>>l;
        add(u,v,l);
        add(v,u,l);
    }
    
    dijkstra();
    
    sort(dist+1,dist+1+n);
    cout<<dist[k+1];
    return 0;
}