ABC335 E

我的做法是 Dijkstra，优先队列中维护的是目前可以到达的且答案不为 0 的点中，点权最小的点。特别地，如果点权相等，目前答案越大越好。

请问这种做法为什么正确？

AC 代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
struct node {
    int id, v, r;
    bool operator< (const node & nd) const { 
        if (v != nd.v) return v > nd.v;
        return r < nd.r;
    }
};
vector<int> g[N];
int n, m, s, e, a[N], vis[N], res[N];
void dijkstra(int st) {
    priority_queue<node> q;
    res[st] = 1;
    q.push({st, a[st], 1});
    while (!q.empty()) {
        int p = q.top().id; q.pop();
        if (vis[p]) continue;
        vis[p] = 1;
        for (int ed : g[p]) {
            if (!vis[ed]) {
                if (a[ed] > a[p]) {
                    res[ed] = max(res[ed], res[p] + 1);
                    q.push({ed, a[ed], res[ed]});
                }
                if (a[ed] == a[p]) {
                    res[ed] = max(res[ed], res[p]);
                    q.push({ed, a[ed], res[ed]});
                }
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &s, &e);
        g[s].push_back(e), g[e].push_back(s);
    }
    dijkstra(1);
    printf("%d", res[n]);
    return 0;
}

如果把重载 < 部分换成：

bool operator< (const node & nd) const { 
    if (v != nd.v) return v > nd.v;
    return r > nd.r;
}

或者是：

bool operator< (const node & nd) const { 
    return v > nd.v;
}

都会 WA.