wa on #9 #11，90分求调

free_man @ 2024-07-28 10:44:01

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define int long long

const int N = 1000010;
int n, m, b;
int f[N], dis[N];
int e[N], ne[N], h[N], idx, w[N];
bool vis[N];

void add(int a, int b, int x) {
    e[idx] = b;
    w[idx] = x;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dijkstra(int k) {
    if (k < f[1]) return -1;
    memset(dis, 0x7f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > hp;
    hp.push({0, 1});
    while (!hp.empty()) {
        // cout << hp.size() << endl;
        auto t = hp.top();
        hp.pop();
        int ver = t.second, d = t.first;
        if (vis[ver]) continue;
        vis[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            // cout << j << endl;
            if (f[j] > k) continue;
            if (dis[j] > d + w[i] && !vis[j]) {
                dis[j] = d + w[i];
                hp.push({dis[j], j});
            }
        }
    }
    // cout << 'd' << endl;
    if (dis[n] == 0x7f7f7f7f) return -1;
    return dis[n];
}

signed main() {
    scanf("%lld%lld%lld", &n, &m, &b);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &f[i]);
    memset(h, -1, sizeof(h));
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%lld%lld%lld", &x, &y, &z);
        if (x != y) {
            add(x, y, z);
            add(y, x, z);
        }
    }

    if (dijkstra(1e9) == -1) {
        printf("AFK\n");
        return 0;
    }
    int l = 0, r = 1e9;
    LL distance;
    while (l < r) {
        int mid = (l + r) >> 1;
        distance = dijkstra(mid);
        if (distance != -1 && distance <= b) r = mid;
        else l = mid + 1;
    }

    if (distance > b) {
        printf("AFK\n");
    } else {
        printf("%lld\n", l);
    }

    return 0;
}

by free_man @ 2024-07-29 10:54:33

已解决，是用0x3f初始化long long导致的，手动初始化一下就可以了

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define int long long

const int N = 1000010;
int n, m, b;
int f[N], dis[N];
int e[N], ne[N], h[N], idx, w[N];
bool vis[N];

void add(int a, int b, int x) {
    e[idx] = b;
    w[idx] = x;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dijkstra(int k) {
    if (k < f[1]) return -1;
    for (int i = 1; i <= n; i++) {
        dis[i] = 1e10;
    }
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > hp;
    hp.push({0, 1});
    while (!hp.empty()) {
        // cout << hp.size() << endl;
        auto t = hp.top();
        hp.pop();
        int ver = t.second, d = t.first;
        if (vis[ver]) continue;
        vis[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            // cout << j << endl;
            if (f[j] > k) continue;
            if (dis[j] > d + w[i] && !vis[j]) {
                dis[j] = d + w[i];
                hp.push({dis[j], j});
            }
        }
    }
    // cout << 'd' << endl;
    if (dis[n] == 1e10) return -1;
    return dis[n];
}

signed main() {
    scanf("%lld%lld%lld", &n, &m, &b);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &f[i]);
    memset(h, -1, sizeof(h));
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%lld%lld%lld", &x, &y, &z);
        if (x != y) {
            add(x, y, z);
            add(y, x, z);
        }
    }

    if (dijkstra(1e9) == -1) {
        printf("AFK\n");
        return 0;
    }
    int l = 0, r = 1e9;
    LL distance;
    while (l < r) {
        int mid = (l + r) >> 1;
        distance = dijkstra(mid);
        if (distance != -1 && distance <= b) r = mid;
        else l = mid + 1;
    }

    if (distance > b) {
        printf("AFK\n");
    } else {
        printf("%lld\n", l);
    }

    return 0;
}