day47-陈宇

T1 CF576D Flights for Regular Customers

• 给定一张 n 个点 m条边的有向图。
• 一开始你在 1 号节点，你要走到 n 号节点去。
• 只有当你已经走过了至少 d_i 条边时，你才能走第 i 条边。
• 问最少要走多少条边，或判断无法到达。
• (n , m le 150 d_i le 10^9)。

solution

简单来说就是，

• 将边按照限制从小到大排序，依次加入

• 用矩阵快速幂维护可达性，再用一个bitset维护1号点可以到达的点。

• 但是矩乘复杂度有点高，又因为矩乘只用维护0 / 1 ， 所以可以用bitset优化。

• 每加入一个边之后，用bfs求一遍ans，更新即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 155;
inline int read()
{
	register int x = 0 , f = 0; register char c = getchar();
	while(c < '0' || c > '9') f |= c == '-' , c = getchar();
	while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48) , c = getchar();
	return f ? -x : x;
}
int n , m;
int dis[N];
struct edge{ int u , v , c; }e[N];
bitset<N> to;
queue<int> q;
struct Matrix
{
	bitset<N> a[N];
	bitset<N> friend operator * (const bitset<N> &A , const Matrix &B)
	{
		bitset<N> C;
		for(int i = 0 ; i < n ; ++i) C[i] = (A & B.a[i]).any();
		return C;
	}
	Matrix friend operator * (const Matrix &A , const Matrix &B)
	{
		Matrix C;
		for(int i = 0 ; i < n ; ++i)
			for(int j = 0 ; j < n ; ++j)
				if(A.a[i][j]) C.a[i] |= B.a[j];
		return C;
	}
}mp;

void ksm(Matrix A , int k , bitset<N> &to)
{
	for( ; k ; k >>= 1 , A = A * A)
		if(k & 1) to = to * A;
}

int main()
{
	n = read(); m = read();
	for(int i = 1 ; i <= m ; ++i) e[i].u = read() - 1 , e[i].v = read() - 1 , e[i].c = read();
	sort(e + 1 , e + 1 + m , [&](const edge &A , const edge &B) { return A.c < B.c; });
	to[0] = 1; int ans = 2e9 , lst = 0;
	for(int i = 1 ; i <= m ; ++i)
	{
		if(e[i].c >= ans) break; ksm(mp , e[i].c - lst , to); lst = e[i].c;
		mp.a[e[i].v][e[i].u] = 1;
		for(int j = 0 ; j < n ; ++j) if(to[j]) dis[j] = 0 , q.push(j); else dis[j] = 2e9;
		while(q.size())
		{
			int x = q.front(); q.pop();
			for(int i = 0 ; i < n ; ++i) if(mp.a[i][x] && dis[i] == 2e9) dis[i] = dis[x] + 1 , q.push(i);
		}
		if(dis[n - 1] < 2e9) ans = min(ans , lst + dis[n - 1]);
	}
	if(ans == 2e9) puts("Impossible"); else cout << ans << '
';
	return 0;	
}