J. Elden Ring
https://codeforces.com/gym/103861/problem/J
题目大意: 给定一个规模为$2e5$的无向图，每个点除了起始点都有一个怪物在那里，第$i$个点的怪物的战力值为$l_i$，我们初始的战力值为$l_1$
我们可以打败怪物当且仅当我们的战力值比怪物的高。怪物每天的战力值会增加$B$，我们杀掉一只怪物增加的战力值为$A$，问我们是否可以到达最终点
解题思路: 考虑这道题和别的题目不一样的地方也就是引入了战力值这个概念，首先我们假设我们的战力值永远不会改变，那么起始也就是对于$A = B$的这一种情况，我们直接$BFS$，并且看当前这个点的战力值是否比起始点要小，符合条件的那么我们就可以加入相对应的队列即可。
然后我们考虑$A < B$的这一种情况，因为我们的战力值是不断减少的，那么我们仍然可以直接$BFS$去找我们可以到达的点，并且比较到达当前点消耗的数值是否比原来的战力值小即可。
最后我们来分析$A > B$的情况，因为$A > B$，所以我们的战力值是在不断增加的。在不断增加的时候我们实际上是可以开放很多点的，那么对于原来的跑图来说我们处理的要么是本身可以到达的，要么是处理因为一些条件不能到达的，因此对于这一张新图来说我们先跑一遍最短路来处理什么点在这种情况下可以先到达。
对于处理这一张新图来说我们首先先把$1$号节点给放进去，然后我们再跑$dij$，优先队列里面放的是当前点的权值和这个点，维护一个小数字在前面的队列。因为小数字在前面，那么我们可以不断增加自己的战力值，因此最后有可能达到一些权值更大的情况。
然后在跑实际天数的时候我们可以直接跑$dij$，但是这里的话使用的是从$1$号节点到当前这个$now$节点所需要的天数,然后对当前的值进行分析，如果比转移点要小的话直接$+1$即可，否则计算以下从$1$号节点转移过来的权值
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const ll inf = 1e18;
vector<int> edge[maxn];
ll n,m,A,B;
ll dis[maxn],vis[maxn],val[maxn];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
for(int Case = 1;Case <= T;++Case)
{
cin >> n >> m >> A >> B;
for(int i = 1;i <= n;++i)
{
edge[i].clear();
dis[i] = inf;
vis[i] = 0;
}
for(int i = 1,u,v;i <= m;++i)
{
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for(int i = 1;i <= n;++i) cin >> val[i],val[i] += B;
val[1] -= B;
if(A == B)
{
queue<int> que;
que.push(1);
dis[1] = 0;
while(!que.empty())
{
auto now = que.front();
que.pop();
for(auto to:edge[now])
{
if(val[to] < val[1] && dis[to] > dis[now])
{
que.push(to);
dis[to] = dis[now] + 1;
}
}
}
cout << (dis[n] == inf ? -1 : dis[n]) << "\n";
}
else if(A < B)
{
queue<int> que;
que.push(1);
dis[1] = 0;
while(!que.empty())
{
auto now = que.front();
que.pop();
for(auto to:edge[now])
{
if(1ll * val[to] + dis[now] * (B - A) * 1ll < val[1] && dis[to] > dis[now])
{
dis[to] = dis[now] + 1;
que.push(to);
}
}
}
cout << (dis[n] == inf ? -1 : dis[n]) << "\n";
}
else
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
int day = -1;
que.push({0,1});
while(!que.empty())
{
auto [nowd,now] = que.top();
que.pop();
if(vis[now]) continue;
if(day != -1 && val[now] >= val[1] + (A - B) * day)
{
break;
}
vis[now] = 1;
day++;
for(auto to:edge[now])
{
if(!vis[to]) que.push({val[to],to});
}
}
dis[1] = 0;
while(!que.empty()) que.pop();
que.push({dis[1],1});
while(!que.empty())
{
auto [nowd,now] = que.top();
que.pop();
if(nowd > dis[now]) continue;
for(auto to:edge[now])
{
if(!vis[to]) continue;
if(val[to] < val[now] && dis[to] > nowd + 1)
{
dis[to] = nowd + 1;
que.push({dis[to],to});
continue;
}
if(dis[to] > max(nowd + 1ll,(val[to] - val[1]) / (A - B) + 2))
{
dis[to] = max(nowd + 1ll,(val[to] - val[1]) / (A - B) + 2);
que.push({dis[to],to});
}
}
}
cout << (dis[n] == inf ? -1 : dis[n]) << "\n";
}
}
}
