[CF576D] Flights for Regular Customers

CF576D
把矩阵定义为 \(f_{t,i,j}\) 表示恰好 t 步后 i,j 是否可达,则广义乘法为

因为是或操作,所以 \(f_{i,j}=1\) 时答案或上另一个乘数的第 j 行即可,bitset 优化。
从小到大扩展 d,这时从恰好 d 步数可达的点 bfs 即可。
Floyd 的 k 在最外层 Floyd 的 k 在最外层 Floyd 的 k 在最外层

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define b1t bitset
const int MAXN=155;
const ll INF=1e18;
void read(int &x){
	x=0;int f=1;char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);s=getchar();
	}
	x*=f;
}
int n,m;
ll dp[MAXN][MAXN],Ans=INF;
struct edg{
	int x,y,d;
	edg(){};
	edg(int X,int Y,int D){
		x=X;y=Y;d=D;
	}
	bool operator<(const edg &a)const{
		return d<a.d;
	}
}ed[MAXN];
struct mat{
	b1t<MAXN> f[MAXN];
	void init(){
		for(int i=1;i<=n;i++) f[i].reset();
	}
}st;
mat operator*(mat a,mat b){
	mat c;
	c.init();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a.f[i][j]) c.f[i]|=b.f[j];
		}
	}
	return c;
}
int main(){
	read(n);read(m);
	for(int i=1;i<=n;i++) st.f[i][i]=1;
	for(int i=1,x,y,z;i<=m;i++){
		read(x);read(y);read(z);
		ed[i]=(edg){x,y,z};
	}
	sort(ed+1,ed+1+m);
	for(int now=1;now<=m;now++){
		mat tmp;tmp.init();
		for(int i=1;i<now;i++){
			tmp.f[ed[i].x][ed[i].y]=1;
		}
		int dis=ed[now].d-ed[now-1].d;
		while(dis){
			if(dis&1) st=st*tmp;
			tmp=tmp*tmp;dis>>=1;
		}	
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j) dp[i][j]=0;
				else dp[i][j]=INF;
			}
		}
		for(int i=1;i<=now;i++){
			dp[ed[i].x][ed[i].y]=1;
		}
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
				}
			}
		}
		for(int i=1;i<=n;i++){
			if(st.f[1][i]) Ans=min(Ans,ed[now].d+dp[i][n]);
		}
	}
	if(Ans==INF) printf("Impossible");
	else printf("%d",Ans);
	return 0;
}