[ cf1407E ] 最短路+思维

E. Egor in the Republic of Dagestan

题意：n个点，m条边的有向图。从1号点出发到n号点。每个边有黑白两色，你需要对点染色，一点可以通过同色边到达另一点，求如何对所有点染色，使1到n的最短距离最大，或者根本不能到达？

题解：从n开始倒着bfs即可。如果第一次遇到某个点，则说明在真的最短路上，为了避免走这条路，我们将该点染成和连边相反的颜色即可。如果之后又遇到这个点则根据颜色来决定是否松弛，并加入队列。

#include
#define ll long long
#define pll pair
#define pii pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define mem0(x) memset(x,0,sizeof(x))
#define meminf(x) memset(x,0x3f,sizeof(x))
#define VI vector
#define VL vector
using namespace  std;

const int N = 5e5+5;
int color[N], dis[N],vis[N];
vector> g(N); 
queue q;
int main(){
    ios::sync_with_stdio(0);
    int n,m;cin>>n>>m;
    rep(i,1,m){
        int u,v,t;
        cin>>u>>v>>t;
        g[v].push_back({u,t}); 
    }
    meminf(dis);memset(color,-1,sizeof(color));
    color[n] = dis[n] = 0;
    
    q.push(n);
    while(!q.empty()){
        int v= q.front();q.pop();
        vis[v] = 1;
        for(auto&it :g[v]){
            int u = it.first,t = it.second;
            if(vis[u]) continue;
            if(color[u]==-1){
                color[u] = 1-t;
            }else{
                if(color[u]==t&&dis[u]>dis[v]+1){
                    dis[u] = dis[v]+1;
                    q.push(u);
                }
            }
        }
    }

    int ans;
    if(dis[1] == 0x3f3f3f3f){
        ans = -1;
    }else{
        ans = dis[1];
    }
    cout<