ecfinal J

分情况讨论：如果的话，就直接跑Dijkstra。否则就先用优先堆模拟出可以到达哪些点，然后对这些点跑Dijkstra，不过dp方程要改变

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

using ll = long long;

ll tt, n, m, A, B, l[(int)2e5 + 9], dis[(int)2e5 + 9];
vi g[(int)2e5 + 9];
bitset<(int)2e5 + 9> vis;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tt;
    f(sb, 1, tt)
    {
        cin >> n >> m >> A >> B;
        for (int i = 1; i <= n; ++i)
            g[i].clear(), dis[i] = 0x3f3f3f3f;
        for (int i = 1, x, y; i <= m; ++i)
        {
            cin >> x >> y;
            g[x].push_back(y), g[y].push_back(x);
        }
        for (int i = 1; i <= n; ++i)
            cin >> l[i], l[i] += i == 1 ? 0ll : B;
        if (A <= B)
        {
            queue<int> qu;
            qu.push(1);
            dis[1] = 0;
            while (!qu.empty())
            {
                auto p = qu.front();
                qu.pop();
                // cerr<<p<<"::"<<dis[p]<<"\n";
                for (auto it : g[p])
                {
                    // cerr<<it<<":::"<<((dis[p]+1)*(A-B)+l[1])<<"\n";
                    if (dis[it] > dis[p] + 1 && dis[p] * (A - B) + l[1] > l[it])
                    {
                        dis[it] = dis[p] + 1;
                        qu.push(it);
                    }
                }
            }
            dis[n] = dis[n] == 0x3f3f3f3f ? -1ll : dis[n];
            cout << dis[n] << "\n";
        }
        else
        {
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
            vis.reset();
            ll day = -1;
            q.push({0,1});
            while (!q.empty())
            {
                auto [aa, bb] = q.top();
                q.pop();
                if (vis[bb])
                    continue;
                if(day!=-1&&aa>=l[1]+day*(A-B))break;
                vis[bb]=1,day+=1;
                for (auto it : g[bb])
                {
                    if (!vis[it])
                        q.push({l[it], it});
                }
            }
            q.push({0, 1});
            dis[1] = 0;
            while (!q.empty())
            {
                auto [aa, bb] = q.top();
                q.pop();
                if (aa>dis[bb])
                    continue;
                for (auto it : g[bb])
                {
                    if(vis[it]&&dis[it]>aa+1&&l[it]<l[1]){
                        dis[it]=aa+1;
                        q.push({dis[it],it});
                    }else if(vis[it]&&dis[it]>max(aa+1ll,(l[it]-l[1])/(A-B)+2)){
                        dis[it]=max(aa+1ll,(l[it]-l[1])/(A-B)+2);
                        q.push({dis[it],it});
                    }
                }
            }
            dis[n]=dis[n]==0x3f3f3f3f?-1ll:dis[n];
            cout << dis[n] << "\n";
        }
    }
}