【Codeforces 576D】Flights for Regular Customers | Mrsrz's blog

bitset，矩阵快速幂

题目大意：

给定一张 $n$ 个点 $m$ 条边的有向图。一条边有一个出现时刻，在该时刻之前不能走，之后一直能走。

现在要从 $1$ 走到 $n$，每个时刻都必须行动。问到达 $n$ 的最早时刻或指出无解。

题解：

考虑将边按出现时间排序，计算出从 $1$ 开始，某个时刻能到达的所有点。

我们用邻接矩阵存边。则每过一个时刻，其转移就类似于当前时刻能到的点的行向量右乘上这个矩阵。这里的矩阵乘法是与或乘法，其性质和加乘是相似的。

自然地想到快速幂。对于两条边之间间隔的那段时间，我们直接快速幂计算，然后再加入新边。

每次加入边的时候，需要判断此时是否能到达终点。如果当前能到达终点，则至多 $n$ 步必定到达终点否则将重复经过一个点，显然不可能。所以新加一条边后，我们只模拟不超过 $n$ 步的情况（如果 $n$ 步里又有新的边则模拟到下一条边出现），之后的直接快速幂转移。

时间复杂度 $O(n^3m\log d)$。

由于矩阵中的信息都是 01，涉及到的都是位运算，所以使用 bitset 优化即可。

时间复杂度 $O(\frac{n^3m\log d}\omega)$。

Code：

#include<iostream>
#include<bitset>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline void failed(){cout<<"Impossible\n",exit(0);}
inline void success(int n){cout<<n<<'\n',exit(0);}
const int N=152;
int n,m,tim;
struct mat{
    bitset<N>b[N];
    int r,c;
    inline bitset<N>&operator[](const int n){return b[n];}
    inline mat operator*(const mat&g)const{
        mat c;
        c.r=r,c.c=g.c;
        for(int i=1;i<=r;++i)
        for(int k=1;k<=g.r;++k)
        if(b[i].test(k))c[i]|=g.b[k];
        return c;
    }
}trans,a;
struct edge{
    int u,v,t;
    inline bool operator<(const edge&rhs)const{return t<rhs.t;}
}e[N];
void pow(mat a,int b,mat&ret){for(;b;b>>=1,a=a*a)if(b&1)ret=ret*a;}
void work(int lst){
    if(tim==lst)return;
    if(lst-tim<=n)
    while(tim<lst){
        ++tim;
        a=a*trans;
        if(a[1].test(n))success(tim);
    }else
    for(int i=1;i<=n;++i){
        ++tim;
        a=a*trans;
        if(a[1].test(n))success(tim);
    }
    if(lst!=tim)pow(trans,lst-tim,a),tim=lst;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    trans.r=trans.c=n;
    a.r=1,a.c=n;
    a[1].set(1);
    for(int i=1;i<=m;++i)cin>>e[i].u>>e[i].v>>e[i].t;
    sort(e+1,e+m+1);
    e[m+1].t=1e9+160;
    tim=0;
    for(int i=1;i<=m+1;++i){
        work(e[i].t);
        trans[e[i].u].set(e[i].v);
    }
    failed();
}