- 给定一张(n)个点(m)条边的有向图，你要从(1)号点走到(n)号点。
- 已知当你走了(d_i)条边之后才能走第(i)条边。
- 问最少要走多少条边才能到达(n)号点。
- (n,mle150,d_ile10^9)
矩乘套路题
考虑(n,m)这么小，(d_i)又这么大，一看就是矩乘的范围了。
于是考虑用矩阵维护每个点是否可到达，把每条已经能走的有向边表示到转移矩阵上去。
至于这种取关键点的做法应该也很套路了。就是先把所有边按(d_i)排个序，然后每次矩阵快速幂做一下相邻两个(d_i)中间的转移（即求出恰好走过(d_i)条边之后能走到的点集），接着修改转移矩阵。
当做到某一条边的时候发现已经能走到(n)了，就从上一条边的状态开始暴力走(n)步。因为在图固定不变时(1)号点到(n)号点的最短路长度显然不可能超过(n)。
但这样的复杂度不太对劲，需要优化。
(bitset)优化矩乘
又是另一个套路了。
考虑这里矩阵维护的是一个点能否到达，也就是说只有(0/1)。
那么我们就可以(bitset)优化，这样就能过了。
代码：(O(frac{n^3mlogd_i}{32}))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 150
using namespace std;
int n,m;struct line {int x,y,t;I bool operator < (Con line& o) Con {return t<o.t;}}s[N+5];
struct M
{
bitset<N+5> a[N+5],b[N+5];I M() {for(RI i=1;i<=n;++i) a[i].reset(),b[i].reset();}
I void Set(CI x,CI y) {a[x].set(y),b[y].set(x);}
I M operator * (Con M& o) Con//bitset优化矩乘
{
M t;for(RI i=1;i<=n;++i) for(RI j=1;j<=n;++j) (a[i]&o.b[j]).any()&&(t.Set(i,j),0);return t;
}
}O,S,U;
I void QP(RI y) {M x=U;W(y) y&1&&(S=S*x,0),x=x*x,y>>=1;}//矩阵快速幂
int main()
{
RI i;for(scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].t);
RI t=0;for(S.Set(1,1),O=S,sort(s+1,s+m+1),i=1;i<=m;O=S,t=s[i++].t)
if(QP(s[i].t-s[i-1].t),U.Set(s[i].x,s[i].y),S.a[1].test(n)) break;//能到达n号点就结束循环
for(i=1;i<=n&&!O.a[1].test(n);++i) O=O*U,++t;//从上一条边开始暴力走n步
return O.a[1].test(n)?printf("%d
",t):puts("Impossible"),0;
}