【题目】D. Flights for Regular Customers
【题意】给定n个点m条边的有向图，每条边有di表示在经过该边前必须先经过di条边，边可重复经过，求1到n的最小经过边数。n,m<=150，di<=10^9，time=4s。
【算法】floyd+矩阵快速幂
【题解】需要计算步数，很容易联想到将floyd中每一步拆成矩阵乘法的经典做法。
令a[d][i][j]表示恰好d步能否从 i 走到 j（邻接矩阵） ，令b[d][i][j]表示当前已走d步时允许通过的边（连边矩阵）。
当前d步时，走一步相当于a[d+1][i][j]=max(a[d][i][k]&&b[d][k][j]),k=1~n（取max 是 或运算），将其定义为一次矩阵乘法就可以用矩阵快速幂优化了。
根据d的不同，连边矩阵b会发生至多m次变化。所以将所有边按d排序后顺序处理，每次快速幂的幂为d[i]-d[i-1]，就能处理出走恰好d步能到达的点（作为起点集）。
最后，每次用1~i的所有边跑一次朴素的最短路（可以用floyd），从起点集到n的最短路+d就是每次的答案，取最小答案。
因为矩阵快速幂中使用的均为01矩阵，所以可以用bitset优化，从而满足时间限制。
复杂度O(m*n^3*log(di)/32+m*n^3)，其中第二部分的最短路还可以用dijkstra算法优化，但已经不必要了。
#include<cstdio> #include<cstring> #include<bitset> #include<algorithm> using namespace std; const int N=160,inf=0x3f3f3f3f; struct cyc{int x,y,d;}e[N]; int n,m,mp[N][N]; bitset<N>a[N],ans[N],c[N],z[N]; bool cmp(cyc a,cyc b){return a.d<b.d;} void mul(bitset<N>a[N],bitset<N>b[N]){ for(int i=1;i<=n;i++)c[i].reset(); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(a[i][k])c[i]|=b[k]; for(int i=1;i<=n;i++)a[i]=c[i]; } int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=m;i++)scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].d); sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++)ans[i].reset(); for(int i=1;i<=n;i++)ans[i][i]=1; int ANS=inf; for(int b=1;b<=m;b++){ for(int i=1;i<=n;i++)a[i].reset(); for(int i=1;i<b;i++)a[e[i].x][e[i].y]=1; int k=e[b].d-e[b-1].d; while(k){ if(k&1)mul(ans,a); mul(a,a); k>>=1; } memset(mp,0x3f,sizeof(mp)); for(int i=1;i<=n;i++)mp[i][i]=0; for(int j=1;j<=b;j++)mp[e[j].x][e[j].y]=1; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); for(int i=1;i<=n;i++)if(ans[1][i])ANS=min(ANS,e[b].d+mp[i][n]); } if(ANS==inf)printf("Impossible");else printf("%d",ANS); return 0; }
代码中要注意的是，因为这里矩阵乘法并不是通常意义上定义的，所以初始值的设置不能沿袭“单位矩阵”等概念，而必须考虑其实际意义。
初始邻接矩阵：全为0，对角线为1，表示初始只能到达自己。（第二轮后可能就不能到达自己了）
连边矩阵：对角线为0，表示不能通过连边到达自己，这样才能使邻接矩阵表示恰好d步的可达信息。
如果连边矩阵的对角线1，即能到达自己，那么表示的就是<=d步的可达信息。