题解：CF1486E Paired Payment

算多维最短路的模板了吧。

类似于 dp，维护三个状态：

$u$ ：遍历到了那个点。
$sc$ ：对于第奇数条边（奇数特指已选了奇数条边），该边权值。
$now$ ：当前是第奇/偶次选择。

以下设

dist

为最短路数组，

w_{a,b}

指

a \to b

的边权。

转移：

dist_{j,w_{u,j},1}=\min_{u \to j}{dist_{u,0,0}}

dist_{j,0,0}=\min_{u \to j} dist_{u,sc,1} + (sc+w_{u,j})^2

最后输出即可。

代码

CPP

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m;
const int N=1e5+10;
int h[N<<2],w[N<<2],e[N<<2],ne[N<<2],idx;
inline void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
long long dist[N][110][2];
bool st[N][110][2];
struct node{
	int u;
	long long sc,dis;
	bool now;
	bool operator<(const node &t)const{
		return dis>t.dis;
	}
};
void dj(){
	priority_queue<node> q;
	q.push({1,0,0,0});
	memset(dist,0x3f,sizeof dist);
	memset(st,0,sizeof st);
	dist[1][0][0]=0;
	while(q.size()){
		node t=q.top();
		q.pop();
		int u=t.u;
		long long sc=t.sc;
		bool now=t.now;
		if(st[u][sc][now]){
			continue;
		}
		st[u][sc][now]=1;
//		cout<<u<<' '<<sc<<' '<<now<<' '<<dist[u][sc][now]<<endl;
		for(int i=h[u];~i;i=ne[i]){
			int j=e[i];
			if(now==0){
				if(dist[j][w[i]][1]>dist[u][0][0]){
					dist[j][w[i]][1]=dist[u][0][0];
					q.push({j,w[i],dist[j][w[i]][1],1});
				}
			}else{
				if(dist[j][0][0]>dist[u][sc][1]+(sc+w[i])*(sc+w[i])){
					dist[j][0][0]=dist[u][sc][1]+(sc+w[i])*(sc+w[i]);
					q.push({j,0,dist[j][0][0],0});
				}
			}
		}
	}
}
long long ans[N];
int main(){
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	dj();
	for(int i=1;i<=n;i++){
		if(dist[i][0][0]>=1e18){
			dist[i][0][0]=-1;
		}
		printf("%lld ",dist[i][0][0]);
	}
	return 0;
}

题解：CF1486E Paired Payment

文章操作

代码

相关推荐

评论

题解：CF1486E Paired Payment