Codeforces 576D Flights for Regular Customers (图论、矩阵乘法、Bitset)

题目链接

http://codeforces.com/contest/576/problem/D

题解

把边按\(t_i\)从小到大排序后枚举\(i\), 求出按前\((i-1)\)条边走\(t_i\)步能到达的点的集合，以它们为起点求\(n\)号点的最短路。

前者等于前\((i-2)\)条边走\(t_{i-1}\)步能到达的点集乘上前\((i-1)\)条边邻接矩阵的\((t_i-t_{i-1})\)次幂。

因为只关心是否存在，故可以使用bitset优化。

时间复杂度\(O(mn^3+\frac{n^3\log T}{\omega})\).

代码

#include<bits/stdc++.h>

using namespace std;

inline int read()

{

	int x = 0,f = 1; char ch = getchar();

	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}

	for(;!isdigit(ch);ch=getchar()) {x = x*10+ch-48;}

	return x*f;

}

const int N = 150;

const int INF = 2e9;

struct AEdge

{

	int u,v,t;

	bool operator <(const AEdge &arg) const {return t<arg.t;}

} ae[N+3];

struct Edge

{

	int v,nxt;

} e[(N<<1)+3];

int a[N+3];

int fe[N+3];

int que[N+3];

int dep[N+3];

bool vis[N+3];

int n,m,en;

void addedge(int u,int v)

{

	en++; e[en].v = v;

	e[en].nxt = fe[u]; fe[u] = en;

}

struct Matrix

{

	bitset<N+3> a[N+3];

	Matrix() {for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j] = 0;}

	Matrix operator *(const Matrix &arg) const

	{

		Matrix ret;

		for(int i=1; i<=n; i++)

		{

			for(int j=1; j<=n; j++)

			{

				if(a[i][j]) {ret.a[i]|=arg.a[j];}

			}

		}

		return ret;

	}

};

Matrix I,O,g,b;

void clearedge()

{

	for(int i=1; i<=n; i++) fe[i] = 0;

	for(int i=1; i<=en; i++) e[i].v = e[i].nxt = 0;

	en = 0;

}

Matrix mquickpow(Matrix x,int y)

{

	Matrix cur = x,ret = I;

	for(int i=0; y; i++)

	{

		if(y&(1<<i)) {y-=(1<<i); ret = ret*cur;}

		cur = cur*cur;

	}

	return ret;

}

void bfs()

{

	for(int i=1; i<=n; i++) vis[i] = false;

	int hd = 1,tl = 0;

	for(int i=1; i<=n; i++) {if(g.a[1][i]) {tl++; que[tl] = i; vis[i] = true; dep[i] = 0;}}

	while(hd<=tl)

	{

		int u = que[hd]; hd++;

		for(int i=fe[u]; i; i=e[i].nxt)

		{

			int v = e[i].v;

			if(!vis[v]) {vis[v] = true; tl++; que[tl] = v; dep[v] = dep[u]+1;}

		}

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1; i<=n; i++) I.a[i].set(i);

	for(int i=1; i<=m; i++)

	{

		scanf("%d%d%d",&ae[i].u,&ae[i].v,&ae[i].t);

	}

	sort(ae+1,ae+m+1);

	g = I;

	int ans = INF;

	for(int i=1; i<=m; i++)

	{

		for(int j=1; j<=i; j++) {addedge(ae[j].u,ae[j].v);}

		g = g*mquickpow(b,ae[i].t-ae[i-1].t);

		bfs();

		if(vis[n]) {ans = min(ans,ae[i].t+dep[n]);}

		clearedge();

		b.a[ae[i].u].set(ae[i].v);

	}

	if(ans==INF) puts("Impossible");

	else printf("%d\n",ans);

	return 0;

}

巴特西

Codeforces 576D Flights for Regular Customers (图论、矩阵乘法、Bitset)

题目链接

题解

代码

最新文章

热门文章