Egor in the Republic of Dagestan

题目链接

题目大意

给一张有向图，边的边权只有0和1，让给点染色，点是0的点只能走边权是0 的边，点是1的点只能走边权是1的边，
有一个人要从1走到n，让给点染色，使这个人走不到n，如果不能让他走不到n，那就让他走的最短路距离最大。
输出最短路的距离和点权。

题解

目的是要把每个点走到n的最短路给封住，
建反向图，从n开始走，如果这是第一次走到点x，就把x的颜色变成跟这个边的颜色不同的颜色，因为第一次走到是最短距离，把这个最短距离封住就好。然后其他的就是最短路了。
为什么要倒着呢？因为这个点的颜色是根据下一个边定的。

#include<algorithm>
#include<iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <stack>
#include <map>
#include <bitset>
#include <set>
#include <unordered_set>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef unsigned long long ull;
typedef unordered_set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b > 0){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};
int lb(int x){
   return  x & -x;}
//friend bool operator < (Node a,Node b) 重载
const int inf = 0x3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 5e5+10;
const int M = 1e6 + 2;
int dis[maxn];
int vis[maxn];
std::vector<pii> vv[maxn];


int main()
{
   
    int n,m;
    scanf("%d%d",&n,&m);
    for (int  i= 1;i <= n; i ++ )
    {
   
        dis[i] = inf;
        vis[i] = -1;
    }
    for (int i = 1; i <= m; i ++ )
    {
   
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        vv[y].pb(mkp(x,v));
    }
    queue<int> qq;
    qq.push(n);
    dis[n] = 0;
    while(!qq.empty())
    {
   
        int x = qq.front();
        qq.pop();
        for (int i = 0; i < vv[x].size(); i ++ )
        {
    
            int v = vv[x][i].st;
            // printf("%d %d %d %d \n",x,v,vv[x][i].sd,vis[v]);
            if(vis[v] == -1)
            {
   
                vis[v] = vv[x][i].sd ^ 1;
            }
            else
            {
   
                // printf("11111 %d %d %d\n",v,vis[v],vv[x][i].sd);
                if(vv[x][i].sd == vis[v] && dis[v] > dis[x] + 1)
                {
   
                    // printf("%d \n",v);
                    dis[v] = dis[x] + 1;
                    qq.push(v);
                }
            }
        }
    }
    if(dis[1] == inf)
    {
   
        printf("-1\n");
    }
    else
        printf("%d\n",dis[1]);
    for (int  i= 1; i <= n; i++ )
    {
   
        if(vis[i] == -1)
            vis[i] = 0;
        printf("%d",vis[i]);
    }
    printf("\n");

}