n<=150个点，m<=150条路，每条路Ai,Bi,Di表示Ai到Bi有一条有向边，使用他前至少要走Di条路，问1到n最少走几条路。
又是n^4过150的题。。。。
不同于传统的最短路，这次的最短路包括了m个图，并且状态和走的路径数有关。所以要一个状态Can(i,j)表示能否到达点i走j步。
由于有m个图，我们就一个一个图来看。把边从小到大加入图，每加入某个值的一组边即可构成一个新图。在进入一个新图之前，我需要知道：在上个图的最后一步，从1走能走到哪些点，已这些点为起点进行下一步的探索。新来一个图之后，先尝试在这个图上走 不进入下个图的边数，能不能走到n点，如果能输出答案，不能就记这个图最后能从一到达哪些点然后进行下一步扩展。而尝试找能否走到n点，不可能从C(i,Dj)一路推到C(i,Dj+1)这里的D排序好了，所以需要一个倍增floyd。
然而这样的话是m*n*n*n*logMax，咋整？floyd用bitset优化！m*n*n*n*logMax/32大概就是n^4啦
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<stdlib.h> 5 #include<bitset> 6 //#include<math.h> 7 //#include<iostream> 8 using namespace std; 9 10 int n,m; 11 #define maxn 161 12 struct Mat 13 { 14 bitset<maxn> a[maxn]; 15 void clear() {for (int i=1;i<=n;i++) a[i].reset();} 16 Mat operator * (const Mat &b) 17 { 18 Mat ans; 19 for (int j=1;j<=n;j++) 20 for (int i=1;i<=n;i++) 21 if (a[i][j]) ans.a[i]|=b.a[j]; 22 return ans; 23 } 24 Mat operator ^ (const Mat &b) 25 { 26 Mat ans; 27 for (int j=1;j<=n;j++) 28 for (int i=1;i<=n;i++) 29 if (a[i][j]) ans.a[i]|=b.a[j]; 30 for (int i=1;i<=n;i++) ans.a[i]|=a[i]; 31 return ans; 32 } 33 }mp,f[33],base; 34 35 struct Point 36 { 37 int a,b,d; 38 bool operator < (const Point &b) const {return d<b.d;} 39 }p[maxn]; 40 int main() 41 { 42 scanf("%d%d",&n,&m); 43 for (int i=1;i<=m;i++) scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].d); 44 sort(p+1,p+1+m); 45 if (p[1].d) {puts("Impossible");return 0;} 46 p[m+1].d=0x3f3f3f3f; 47 base.a[1][1]=1; 48 for (int i=2;i<=m+1;i++) 49 { 50 while (i<=m+1 && p[i].d==p[i-1].d) {mp.a[p[i-1].a][p[i-1].b]=1; i++;} 51 int j,num=p[i].d-p[i-1].d; 52 for (j=30;j>=0;j--) if ((1<<j)<=num) break; 53 f[0]=mp; 54 for (int k=1;k<=j;k++) f[k]=f[k-1]^f[k-1]; 55 Mat now; now=base; int cnt=0; 56 for (int k=j;k>=0;k--) if (cnt+(1<<k)<=num) 57 { 58 Mat tmp;tmp=now^f[k]; 59 bool flag=0; 60 for (int l=1;l<=n;l++) flag|=tmp.a[l][n]; 61 if (!flag) cnt+=(1<<k),now=tmp; 62 } 63 if (cnt!=num) {printf("%d ",p[i-1].d+cnt+1);return 0;} 64 else 65 { 66 f[0]=mp; 67 for (int k=1;k<=j;k++) f[k]=f[k-1]*f[k-1]; 68 cnt=0; 69 for (int k=j;k>=0;k--) if (cnt+(1<<k)<=num) base=base*f[k],cnt+=(1<<k); 70 Mat tmp; tmp=base; 71 base.clear(); 72 for (int k=1;k<=n;k++) 73 for (int l=1;l<=n;l++) 74 if (tmp.a[k][l]) base.a[l][l]=1; 75 } 76 } 77 puts("Impossible"); 78 return 0; 79 }