自动搬运

查看原文

来自洛谷，原作者为

	sand_fish 如鲸向海，似鸟投林

搬运于2025-08-24 23:08:01，当前版本为作者最后更新于2025-02-27 23:19:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给你一个图，每个点都有点权，求从每个点出发点权减去路径花费的最大值。

思路

首先显而易见的是去掉点权这个条件，这题就是个单源最短路模版。

那点权怎么搞呢？我们可以直接建一个超级源点连接每一个点，边权为点权的相反数，这样我们就可以用最短路求最大。

所以拿单源最短路模板加上一个超级源点就过了！

代码

#include <bits/stdc++.h>
using namespace std; 
#define pi pair<int, int> //简化代码 
const int N = 3000001; //这里是无向图 + 超级源点 所以要开 n+m*2 
int cnt, h[N], nex[N], to[N], w[N]; //链式前向星存图 
int n, m, dis[N];
bool vi[N]; //判断是否走过 
void ad(int u, int v, int ww) { //建边 
	nex[++cnt] = h[u];
	to[cnt] = v;
	w[cnt] = ww;
	h[u] = cnt;
}
void dj(int s) { //模板 这里不多说 
	memset(dis, 0x3f, sizeof dis);
	memset(vi, 0, sizeof vi); //memset常数大但我爱用 
	priority_queue<pi, vector<pi>, greater<pi> > q;
	q.push({0, s});
	while(!q.empty()) { 
		int u=q.top().second, d=q.top().first;
		q.pop();
		if(vi[u]) continue;
		vi[u] = 1;
		for(int i=h[u]; i; i=nex[i]) {
			int v=to[i], ww=w[i];
			if(d+ww < dis[v]) {
				dis[v] = d+ww;
				q.push({dis[v], v});
			}
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i=1, ww; i<=n; i++)
		scanf("%d", &ww), ad(0, i, -ww); //超级源点 
	while(m--) {
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		ad(a, b, c); ad(b, a, c); //由于是无向图所以要建双向边 
	}
	dj(0); //从超级源点开始跑 
	for(int i=1; i<=n; i++)
		printf("%d\n", -dis[i]); //注意输出相反数 
	return 0;
}

蒟蒻在洛谷上的第一篇题解，求过审啊啊啊！！

Thanks

For Your Watching