题目概述

CF1407E

解题报告

这题好妙啊……如果正着做，那么一个城市的颜色决定了好多边，但是倒着做的话，一条边决定了一座城市的颜色，明显好考虑了很多。

从 $n$ 出发做最短路，记录 $dis_{x,0}$ 表示 $x$ 点颜色为 $0$ 的最短路，$dis_{x,1}$ 表示 $x$ 点颜色为 $1$ 的最短路，为了使最短路最长，我们记 $f_x=max\{dis_{x,0},dis_{x,1}\}$ ，然后用 $f$ 更新 $dis$ 做最短路。

根据 $f_1$ 就可以判断是否可能让最短路不存在，输出方案只需要看 $dis_{x,0}$ 大还是 $dis_{x,1}$ 大，哪个大说明染成了哪个颜色。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=500000,maxm=500000;

int n,m,dis[maxn+5][2],MAX[maxn+5];
int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5],w[maxm+5];
int que[maxn+5];bool vis[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
int main(){
    freopen("E.in","r",stdin);freopen("E.out","w",stdout);
    readi(n);readi(m);
    for (int i=1,x,y,z;i<=m;i++) readi(x),readi(y),readi(z),Add(y,x,z);
    for (int i=1;i<n;i++) dis[i][0]=dis[i][1]=MAX[i]=1e9;
    int Head=0,Tail=0;que[++Tail]=n;vis[n]=true;
    while (Head!=Tail){
        int x=que[Head=(Head+1)%maxn];vis[x]=false;
        for (int j=lnk[x],u;j;j=nxt[j])
            if (MAX[x]+1<dis[u=son[j]][w[j]]){
                dis[u][w[j]]=MAX[x]+1;
                MAX[u]=max(dis[u][0],dis[u][1]);
                if (!vis[u]) que[Tail=(Tail+1)%maxn]=u,vis[u]=true;
            }
    }
    if (MAX[1]<1e9) printf("%d\n",MAX[1]); else puts("-1");
    for (int i=1;i<=n;i++) putchar((dis[i][1]>dis[i][0])+48);
    return 0;
}