又是有向图。。。

不同于传统的最短路，当我们走到一个节点的时候，还要记录此时经过的边数才能完成转移。但是第二维太大了，太抽象了！

看到$m$这么小，很难不想到离散化。那么设$f_{i,j}$表示当第$i$条边出现时，在节点$j$是否可行，注意这是$01$状态。转移非常粗暴，因为我们要在当前的边集下逗留$d_{i+1}-d_i$步，所以直接每次跳$2^i$步即可。

算一下复杂度，居然是$n^{3}m\log V$，因为每加入一条边都要跑一遍$\text{Floyd}$，太抽象了！！因为是$01$状态所以可以用$\text{bitset}$优化，这样复杂度$\frac{n^3}{w}m\log V$，这样算下来已经可以通过了。。。

发现问题瓶颈在于计算邻接矩阵的$k$次幂上面，可以采取动态加边的思想来维护，然后因为左乘的是一个向量（哪些点可达），所以这一部分也可以少一个$n$。这样复杂度$\frac{n^2}{w}m\log V$。但是为什么没有人写这个做法呢？

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=155;
int n,m,res=0x3f3f3f3f,dis[N];
queue<int>Q;
struct node{bitset<N>f[N];node(){for(int i=1;i<=n;i++)f[i].reset();}node operator *(const node &a)const{node r;for(int i=1;i<=n;i++)assert(r.f[i].count()==0);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(f[i][j]){r.f[i]|=a.f[j];}}}return r;}
}f,mat;
struct edge{int x,y,d;bool operator <(const edge &a)const{return d<a.d;}
}edges[N];
bitset<N>arrays;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++)cin>>edges[i].x>>edges[i].y>>edges[i].d;sort(edges+1,edges+1+m);arrays[1]=1;for(int i=1;i<=m;i++){int x=edges[i].x,y=edges[i].y,k=edges[i].d-edges[i-1].d;f=mat;for(;k;k>>=1){if(k&1){bitset<N>tmp;for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){if(f.f[j][k]&&arrays[j])tmp[k]=1;}}arrays=tmp;}f=f*f;}mat.f[x][y]=1;memset(dis,0x3f,sizeof dis);for(int j=1;j<=n;j++){if(arrays[j]){Q.push(j),dis[j]=edges[i].d;}}while(Q.size()){int u=Q.front();Q.pop();for(int v=1;v<=n;v++){if(mat.f[u][v]&&dis[u]+1<dis[v]){dis[v]=dis[u]+1;Q.push(v);}}}res=min(res,dis[n]);}if(res==0x3f3f3f3f)cout<<"Impossible";else cout<<res;
}