P11514 [CCO 2024] Treasure Hunt 题解

· · 题解

题目大意

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

思路

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

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

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

代码

#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