题解：P11819 [PA 2019 Final] Floyd-Warshall

首先两点之间的距离用

n

次 Dijkstra 就可以了。

然后考虑什么样的边会被正确求出：

假设正在求

(x,y)

：

若 $x$ ， $y$ 间有边，则边权等于正常求法下的 $dist_{x,y}$ 。
存在一个点 $p$ 使得 $dist_{x,p}$ 和 $dist_{p,y}$ 能正确求出，且在正常求法下 $dist_{x,p} + dist_{p,y} = dist_{x,y}$ 。

用 bitset 维护即可（代码中的

c_{i,j}

指的是从当前节点出发，

i

为终点，

j

是否可做“转移点”）。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using namespace std;
using PII=pair<int,int>;
const int maxn=2e3+5;
const int maxm=2*maxn;
const int INF=0x3f3f3f3f3f3f3f3fll;
int n,m;

namespace Graph
{
	int head[maxn],tot_edge;
	struct edge
	{
		int v,w,next;
	}e[maxm];
	void G_init()
	{
		memset(head,-1,sizeof(head));
		tot_edge=-1;
	}
	void add(int u,int v,int w)
	{
		e[++tot_edge]=(edge){v,w,head[u]};
		head[u]=tot_edge;
	}
} using namespace Graph;

bitset<maxn> s[maxn],t[maxn],c[maxn];
int D[maxn][maxn];
int dist[maxn];
bool vis[maxn];
priority_queue<PII,vector<PII>,greater<PII> >q;
void Dijkstra(int s)
{
	int i;
	memset(dist,0x3f,sizeof(dist));
	memset(vis,0,sizeof(vis)); 
	dist[s]=0; q.push(mp(0,s));
	while(q.size())
	{
		int x=q.top().se;
		q.pop();
		if(vis[x])
		continue;
		vis[x]=1;
		for(i=head[x];~i;i=e[i].next)
		{
			int y=e[i].v;
			if(dist[y]>dist[x]+e[i].w)
			{
				dist[y]=dist[x]+e[i].w;
				q.push(mp(dist[y],y));
			}
		}
	}
	for(i=1;i<=n;i++) D[s][i]=dist[i];
}
void GetC(int s)
{
	int i;
	for(i=1;i<=n;i++) c[i].reset();
	memset(dist,0x3f,sizeof(dist));
	memset(vis,0,sizeof(vis)); 
	dist[s]=0; q.push(mp(0,s));
	while(q.size())
	{
		int x=q.top().se;
		q.pop();
		if(vis[x])
		continue;
		vis[x]=1;
		for(i=head[x];~i;i=e[i].next)
		{
			int y=e[i].v;
			if(dist[y]>dist[x]+e[i].w)
			{
				dist[y]=dist[x]+e[i].w;
				c[y]=c[x]; c[y][x]=1;
				q.push(mp(dist[y],y));
			}
			else
			if(dist[y]==dist[x]+e[i].w)
			{
				c[y]|=c[x];
				c[y][x]=1;
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int i,j,u,v,w,x,y;
	cin>>n>>m;
	G_init();
	for(i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(i=1;i<=n;i++)
	Dijkstra(i);
	for(i=1;i<=n;i++)
	s[i][i]=t[i][i]=1;
	for(x=1;x<=n;x++)
	{
		for(i=head[x];~i;i=e[i].next)
		{
			int y=e[i].v;
			if(D[x][y]==e[i].w)
			s[x][y]=t[y][x]=1;
		}
	}
	for(x=1;x<=n;x++)
	{
		GetC(x);
		for(y=1;y<=n;y++)
		{
			if((s[x]&t[y]&c[y]).any())
			s[x][y]=t[y][x]=1;
		}
	}
	int ans=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		ans+=(D[i][j]<=INF/2 && !s[i][j]);
	}
	cout<<ans<<'\n';
	return 0;
}

题解：P11819 [PA 2019 Final] Floyd-Warshall

文章操作

相关推荐

评论

题解：P11819 [PA 2019 Final] Floyd-Warshall