不开O2 0分，开O2RE，求助

P1462 通往奥格瑞玛的道路

Chinshyo @ 2023-08-14 00:18:16

求助大佬们

  1. 不懂为什么开O2会RE,而且开O2前后T的点不一样
  2. 求大佬看看这个算法怎么优化，没开O2T了。实在不太会优化了，我直接小根堆优化的dij+二分（找钱的方案），用的第二篇题解的思路
  3. 不太懂为什么会WA，有什么特殊情况要判断吗

开O2

不开O2

#include<bits/stdc++.h>
using namespace std;

const int N = 50005, M = 50005;
int f[N], dis[N], n, m, b;
bool vis[N];
int head[N], ver[M], edge[M], nxt[M], num = 0; //Chain Forward Star

void add(int x, int y, int c) {
    ver[++num] = y, edge[num] = c;
    nxt[num] = head[x], head[x] = num;
}

priority_queue < pair<int, int> > q;

bool chk(int cst) {
    for(int i = 1; i <= n; i++) {
        dis[i] = INT_MAX;
        vis[i] = 0; 
    }

    q.push(make_pair(0, 1));
    dis[1] = 0;
    while(!q.empty()) {
        pair <int, int> p = q.top();
        q.pop();
        int dist = -p.first, x = p.second;
        if(x == n) {
            if(dis[n] > b) return false;
            return true;
        }
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i > 0; i = nxt[i]) {
            int y = ver[i], c = edge[i];
            if(dist + c < dis[y] && f[y] <= cst)  {
                dis[y] = dist + c;
//              cout  << y << "》》"<< dis[y] << endl;
                q.push(make_pair(-dis[y], y));
            }
        }
    }
//  for(int i = 1; i <= n; i++)
//      cout << dis[i] << " ";
//  cout << endl;
//  if(dis[n] <= cst) return true;
//  return false;
}

int main() {
//  freopen("a.aaa" , "w", stdout);
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i++) cin >> f[i];

    int x, y, c;
    for(int i = 1; i <= m; i++) {
        cin >> x >> y >> c;
        add(x, y, c);
        add(y, x, c);
    }

    long long l = 1, r = 1000000005;
    long long mid = (l + r) >> 1;
    while(l <= r) {
        bool tmp = chk(mid);
//      cout << l << " " << r << " " << tmp<< endl;
        if(tmp == 1) {
//          cout  << " Hello " << r << endl;
            r = mid - 1;

            mid = (l + r) >> 1;
        } else {
            l = mid + 1;
            mid = (l + r) >> 1;
        }
    } 
    cout << l << endl; 
    return 0;
}

by DYYqwq @ 2023-08-14 07:28:47

？双向边你不得开二倍数组吗

by DYYqwq @ 2023-08-14 07:31:11

q.push(make_pair(-dis[y], y));

这是干嘛的。

应该是

q.push(make_pair(dis[y], y));

by DYYqwq @ 2023-08-14 07:43:58

#include<bits/stdc++.h>
using namespace std;

const int N = 100005, M = 100005;
int f[N], dis[N], n, m, b;
bool vis[N];
int head[N], ver[M], edge[M], nxt[M], num = 0; //Chain Forward Star

void add(int x, int y, int c) {
    ver[++num] = y, edge[num] = c;
    nxt[num] = head[x], head[x] = num;
}

priority_queue < pair<int, int> > q;

bool chk(int cst) {
    memset(dis , 0x3f , sizeof(dis));
    for(int i = 1; i <= n; i++) {
        vis[i] = 0; 
    }

    q.push(make_pair(0, 1));
    dis[1] = 0;
    while(!q.empty()) {
        pair <int, int> p = q.top();
        q.pop();
        int dist = p.first, x = p.second;
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i > 0; i = nxt[i]) {
            int y = ver[i], c = edge[i];
            if(dist + c < dis[y] && f[y] <= cst)  {
                dis[y] = dist + c;
//              cout  << y << "》》"<< dis[y] << endl;
                q.push(make_pair(dis[y], y));
            }
        }
    }
    if(dis[n] > b) return true;
    return false;
}

int main() {
//  freopen("a.aaa" , "w", stdout);
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i++) cin >> f[i];

    int x, y, c;
    for(int i = 1; i <= m; i++) {
        cin >> x >> y >> c;
        add(x, y, c);
        add(y, x, c);
    }

    long long l = 1, r = 1000000005;
    long long mid = (l + r) >> 1;
    while(l < r) {
        mid = (l + r) >> 1;
        bool tmp = chk(mid);
//      cout << l << " " << r << " " << tmp<< endl;
        if(tmp == 1) {
//          cout  << " Hello " << r << endl;
            l = mid + 1;

        } else {
            r = mid;
        }
    } 
    if(r == 1000000005) cout << "AFK" << endl;
    else cout << l << endl; 
    return 0;
}

by DYYqwq @ 2023-08-14 07:44:34

我先只能这样了，我到学校再给你改qwq

by Chinshyo @ 2023-08-14 08:27:03

@DYYqwq 开的大根堆当小根堆用不是push和top的时候要取反么/kel，我看的《算法竞赛进阶指南》上是这么做的就学了

by Chinshyo @ 2023-08-14 08:27:33

@DYYqwq 啊确实要二倍！

by Chinshyo @ 2023-08-14 08:29:39

@DYYqwq 谢谢大佬！过了好几个点了，T也没了，数组的问题

只剩下Wa了

我下载个数据调调

by DYYqwq @ 2023-08-14 08:33:46

@qxhAwA 嗯嗯，那你调吧，我先做题惹qwq

by Chinshyo @ 2023-08-14 08:35:51

@DYYqwq 啊啊啊我智障，还没判断AFK（（（

|