拓扑排序+二分答案+建图

题目：

Description

不知目标为何地只想越走越远，
将带不走的一切留在梦里。
因为曾经选择的都是我钟爱的事物，
才铸就今天的我。

——《魔女之旅》

灰之魔女伊雷娜，一名只想着旅行的天才少女。

一天，她来到了某个国家。这个国家由nn个风格不同的城市和mm条单向通道组成，每个通道都有一个路程值。现在伊雷娜在11号城市，她想参观至少kk个城市（包括11号城市）。她听说星尘魔女在xx号城市，因此一定要经过xx号城市。

旅行需要食物，每完成一段路程，她都要吃掉和路程值相等的空间的食物。她可以在每个城市进行食物的补充，但是只能在11号城市购买装食物的背包。因为背包空间越大，价格越贵，所以伊雷娜想知道背包空间最少是多少？（贫穷.jpg）


Input
第一行有三个整数n,m,k,x(1\le n\le 10^5,\, 1\le m\le 10^6,\, 1\le k\le n, 1\le x\le n)n,m,k,x(1≤n≤10 
5
 ,1≤m≤10 
6
 ,1≤k≤n,1≤x≤n)接下来mm行每行三个整数u,v,w\;(1\le u,v \le n;\; 1\le w \le 10^9)u,v,w(1≤u,v≤n;1≤w≤10 
9
 )，表示城市uu到城市vv有一条长度为ww的单向通道。数据保证没有环，且有解。


Output
一个整数，表示背包最小空间。


Sample Input 1 

5 7 4 2
1 2 1
1 4 6
4 2 4
4 5 1
2 5 5
3 4 4
1 3 5
Sample Output 1

5
Sample Input 2 

5 7 4 2
1 2 1
1 4 6
4 2 4
4 5 1
2 5 5
3 4 4
1 3 7
Sample Output 2

6
Source

cyh

代码：

#include 
using namespace std;
#define ri register int 
#define M 100005

struct edge{
    int v,val;
    edge(){}
    edge(int a,int b){v=a,val=b;}
}; 
vector p1[M],p2[M];
vector<int> p[M];

int n,m,K,X;
int l,r;
int vis[M];
int du[M];
void dfs1(int u,int a)
{
    vis[u]=1;
    for(ri i=0;i)
    {
        int v=p2[u][i].v;
        int val=p2[u][i].val;
        if(val<=a)
        {
           p[u].push_back(v);    
           du[v]++;
           if(vis[v])continue;
           dfs1(v,a);
        }
    }
}
void dfs2(int u,int a)
{
    vis[u]=1;
    for(ri i=0;i)
    {
        int v=p1[u][i].v;
        int val=p1[u][i].val;
        if(val<=a)
        {
           p[u].push_back(v);    
           du[v]++;
           if(vis[v])continue;
           dfs2(v,a);
        }
    }
}
int len1[M];
queue <int> q;

void bfs1(int u)
{
    while(!q.empty()) q.pop();
    q.push(u);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        if(u==1) break;
        for(ri i=0;i)
        {
          int v=p[u][i];
          len1[v]=max(len1[v],len1[u]+1);
          du[v]--;
          if(du[v]==0) q.push(v);
        }
    }
    
}
int len2[M];
int mx;
void bfs2(int u)
{
    while(!q.empty()) q.pop();
    q.push(u);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        mx=max(mx,len2[u]);
        if(len2[u]+len1[1]+1>=K) break;
        for(ri i=0;i)
        {
          int v=p[u][i];
          len2[v]=max(len2[v],len2[u]+1);
          du[v]--;
          if(du[v]==0) q.push(v);
        } 
    }
}
bool chick(int a)
{
    
    memset(vis,0,sizeof(vis));
    memset(du,0,sizeof(du));
    for(ri i=1;i<=n;i++) p[i].clear();
    dfs1(X,a);    ///
    
    memset(len1,0,sizeof(len1));
    bfs1(X);
    if(!len1[1]&&X!=1) return 0;
    
    
    memset(vis,0,sizeof(vis));
    memset(du,0,sizeof(du));
    for(ri i=1;i<=n;i++) p[i].clear();
    dfs2(X,a);
    
    memset(len2,0,sizeof(len2));mx=0;
    bfs2(X);
    
    if(mx+len1[1]+1>=K) return 1;
    else return 0;  /////// 记住bool 函数 你不返回的值的话，就是返回一，是还存在的。所以一定要把条件返回完。 
    
}
int ans;
void solvee()
{
    //printf("%d %d\n",l,r);
    while(l<=r)
    {
        int mid=(l+r)>>1;
        
        if(chick(mid))
        {
            //printf("%d ",mid);
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d",ans);
}
int main(){

    
    scanf("%d%d%d%d",&n,&m,&K,&X);
    
    l=INT_MAX,r=0;
    for(ri i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge t=edge(b,c);
        p1[a].push_back(t);
        t=edge(a,c);
        p2[b].push_back(t);
        l=min(l,c);
        r=max(r,c);
    }
    solvee();
    return 0;
}

思考： 二分答案的运用：

            1 相当于减少了一维的思维情况

            2 答案是那种单个的？，而且一定是单调的；

注意：1 bool 函数不自己主动返回的话，就会返回1 ，特别强调

           2 当目的城市==1 时 特别注意，这种特殊点，很坑人的；做完题后就想想特殊情况；