正题

题目链接:https://www.luogu.com.cn/problem/P6880

题目大意

给出\(n\)个点\(m\)条边的有向图，边有边权和一个翻转权值。

翻转至多一条边使得\(1->n->1\)往返的权值加上翻转权值最小。

\(1\leq n\leq 200,1\leq m\leq 5\times 10^4\)

解题思路

考虑到\(n\)很小可以从这个方向入手。

有时翻转会使得最短路变长，这个时候当且仅当这条边是最短路的必经边，而图上最多有\(n-1\)条必经边，所以我们如果翻转必经边时直接暴力重新计算一次最短路，否则我们就用预处理的信息来计算。

因为点很少，暴力的\(dij\)比堆优化快

时间复杂度\(O(n(n^2+m))\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

#define mp(x,y) make_pair(x,y)

using namespace std;

const ll N=210,M=5e4+10;

struct node{

	ll to,next,w,v,ban;

}a[M<<1];

ll n,m,tot,ls[N],f[N],g[N],F[N],G[N],ff[N],gg[N],from[N],grom[N],ans;

bool v[N];

void addl(ll x,ll y,ll w,ll v,ll ban){

	a[++tot].to=y;

	a[tot].next=ls[x];

	a[tot].v=v;a[tot].ban=ban;

	ls[x]=tot;a[tot].w=w;

	return;

}

void dij(ll *f,ll s,ll op=0){

	memset(v,0,sizeof(v));f[s]=0;

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

		int x=0;

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

			if(!v[j])x=(f[j]<f[x])?j:x;

		v[x]=1;

		for(ll i=ls[x];i;i=a[i].next){

			ll y=a[i].to;

			if(a[i].ban)continue;

			if(f[x]+a[i].w<f[y]){

				f[y]=f[x]+a[i].w;

				if(op==1)from[y]=i;

				if(op==2)grom[y]=i;

			}

		}

	}

	return;

}

void bij(ll *f,ll s,ll op=0){

	memset(v,0,sizeof(v));f[s]=0;

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

		int x=0;

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

			if(!v[j])x=(f[j]<f[x])?j:x;

		v[x]=1;

		for(ll i=ls[x];i;i=a[i].next){

			ll y=a[i].to;

			if(!a[i].ban)continue;

			if(f[x]+a[i].w<f[y])

				f[y]=f[x]+a[i].w;

		}

	}

	return;

}

signed main()

{

	scanf("%lld%lld",&n,&m);tot=1;

	for(ll i=1;i<=m;i++){

		ll x,y,c,d;

		scanf("%lld%lld%lld%lld",&x,&y,&c,&d);

		addl(x,y,c,d,0);addl(y,x,c,d,1);

	}

	memset(f,0x3f,sizeof(f));dij(f,1,1);

	memset(g,0x3f,sizeof(g));dij(g,n,2);

	memset(F,0x3f,sizeof(F));bij(F,n);

	memset(G,0x3f,sizeof(G));bij(G,1);

	ans=f[n]+g[1];

	for(ll x=1;x<=n;x++){

		for(ll i=ls[x];i;i=a[i].next){

			if(a[i].ban)continue;

			ll y=a[i].to,w1=f[n],w2=g[1];

			if(f[x]+a[i].w+F[y]==f[n]&&i==from[y]){

				a[i].ban=1;a[i^1].ban=0;

				memset(ff,0x3f,sizeof(ff));dij(ff,1);

				w1=ff[n];a[i].ban=0;a[i^1].ban=1;

			}

			else w1=min(w1,f[y]+a[i].w+F[x]);

			if(g[x]+a[i].w+G[y]==g[1]&&i==grom[y]){

				a[i].ban=1;a[i^1].ban=0;

				memset(gg,0x3f,sizeof(gg));dij(gg,n);

				w2=gg[1];a[i].ban=0;a[i^1].ban=1;

			}

			else w2=min(w2,g[y]+a[i].w+G[x]);

			ans=min(ans,w1+w2+a[i].v);

		}

	}

	if(ans>=2e18)puts("-1");

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

	return 0;

}

巴特西

P6880-[JOI 2020 Final]オリンピックバス【最短路】

正题

题目大意

解题思路

code

最新文章

热门文章