[HOJ 190]攻略路徑

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

這題題目敘述我看了七遍還是不知道它在幹嘛
網路上找到code之後，把code看懂了，回頭看題目，才知道它在講甚麼=ㄦ=
看來我的理解能力有問題XD
名詞翻譯:
蘿莉->節點
主線->節點
flag事件->邊
難度值->邊權
攻略路徑->起點為s的任意路徑(不須走完所有點)

可以二分搜路徑長度，數數看小於目前長度的路徑有幾條，然後就可以知道第K長的路徑在哪個長度裡面了
注意在Dfs的時候有可能出現同一個節點被拜訪100000次，這節點恰巧也連出100000條邊，所以你的方法是遍歷臨邊，找長度在規定以內的下去Dfs，會需要100000^2的時間，就TLE了
剪枝的方法是先將邊依照權重排序，遍歷臨邊時，當目前長度+目前權重超過規定馬上break就好了

code:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge
{
    int to,cost;
    Edge(){}
    Edge(const int _t,const int _c):to(_t),cost(_c){}
    bool operator<(const Edge &e)const{return cost<e.cost;}
};
vector<Edge>ET[100000];
int N,M,K,S;
bool Dfs(const int u,const int remain,int &counter)
{
    if(++counter==K)return true;
    for(const Edge &e:ET[u])
    {
        if(e.cost>remain)break;
        if(Dfs(e.to,remain-e.cost,counter))return true;
    }
    return false;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d%d%d",&N,&M,&K,&S)==4)
    {
        S--;
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=0,a,b,c;i<M;i++)
        {
            scanf("%d%d%d",&a,&b,&c),a--,b--;
            ET[a].push_back(Edge(b,c));
        }
        for(int i=0;i<N;i++)sort(ET[i].begin(),ET[i].end());
        int l=0,r=100000000;
        while(l<r)
        {
            const int mid=(l+r)/2;
            int tmp=0;
            if(Dfs(S,mid,tmp))r=mid;
            else l=mid+1;
        }
        printf("%d\n",r);
    }
    return 0;
}