[HOJ] 190 - 攻略路徑

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
struct P{
    int x,y;
}in;
int cmp(P a,P b){
    return a.y<b.y;
}
vector<P> s[100005];
int k,p,cnt,t;
void dfs(int r,int ans){
    cnt++;
    if(cnt>=k) return;
    for(int i=0;i<s[r].size();i++){
        in=s[r][i];
        if(ans+in.y<=t) dfs(in.x,ans+in.y);
        else break;
        if(cnt>k) break;
    }
}
int main(){
    int n,m,x,y,z,i,j;
    while(scanf("%d%d%d%d",&n,&m,&k,&p)!=EOF){
        memset(s,0,sizeof(s));
        for(i=0;i<m;i++){
            scanf("%d%d%d",&x,&y,&z);
            s[x].push_back((P){y,z});
        }
        for(i=1;i<=n;i++)
            sort(s[i].begin(),s[i].end(),cmp);
        int L=-1,R=500000005;
        while(L+1!=R){
            t=(L+R)/2;
            cnt=0;
            dfs(p,0);
            if(cnt>=k) R=t;
            else L=t;
        }
        printf("%d\n",R);
    }
}