[数据结构与算法]AtCoder Beginner Contest 237「E 」「思维 + 最短路」

E - Skiing

题目描述：

n个点，m条边，给出这n个点的高度，u到v的价值是h[u]>=h[v] ? h[u]-h[v] : 2 * (h[v] - h[u])，问从1号点经历任意条边能得到的最大价值是多少

思路：

很有意思的一道题，这里我们可以将幸福值转换成边权进而转换成最长路问题，对于u->v的权值为h[u]>=h[v] ? h[u]-h[v] : 2 * (h[v] - h[u])，但是权值有负数，所以迪杰斯特拉跑不了，用SPFA，发现他死了，所以要想个别的方法

可以发现对于纯下坡的那种边，其价值只与起点和终点的高度有关即h[u]-h[v](假设u是起点，v是终点)，而高度差其实就是向下走加上一倍的权值，向上走加上一倍权值，但是题意说向上走要加上两倍权值，所以我们要让最终权值最大，就得让向上的权值最小，所以对于非下坡的边，从u到v，我们可以设它的边权是h[v]-h[u](>=0)，对于上坡的边，它的权值设为0，跑最短路，得到从1号点到每个点到最短上坡的路程dis[i]，这样到达每个点能产生的价值就是h[1]-h[i]-dis[i]，求个max就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int a, b, c;
vector<int>tr[MAX];
int h[MAX];

int dis[MAX];
int vis[MAX];

void dijkstra(){
    priority_queue<pii, vector<pii>, greater<pii> >q;
    q.push({0, 1});
    mem(dis, inf);
    dis[1] = 0;
    while (!q.empty()) {
        auto [d, u] = q.top();q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(auto v : tr[u]){
            int c = max(0ll, h[v] - h[u]);
            if(dis[v] > dis[u] + c){
                dis[v] = dis[u] + c;
                q.push(m_p(dis[v], v));
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        ans = max(ans, h[1] - h[i] - dis[i]);
    }
    cout << ans << endl;
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> h[i];
    for(int i = 1; i <= m; ++i){
        cin >> a >> b;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    dijkstra();
}


signed main(){
    io;
    work();
    return 0;
}