abc237 E(spfa已死)

题目 题意: 给定n个点的点权值hi，m条边。规定有向边(u,v)的边权为 hu - hv (hu > hv) -2(hu - hv) (hu < hv) 0 (hu = hv) 求点1到其他点的最长路。 思路: 所有边取反然后spfa跑最短路，赛后加强数据以后就不行了。考虑用Dij跑最短路，把所有边取反，但是有负边权，需要换一种建图方式。把所有诸如的(u,v)边都加上 h[u] + h[v].这样就没有负边权了。自己推一下对于势能的影响。 p’ = p + (h[st] - h[ed]). 时间复杂度: O(nlogm) 代码:

// Problem: E - Skiing
// Contest: AtCoder - AtCoder Beginner Contest 237
// URL: https://atcoder.jp/contests/abc237/tasks/abc237_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i