30分/0分警示后人

Wu1hong2shen3_why_42 @ 2023-08-11 20:20:37

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int T = 2e6+10;
struct eee {
    int to,nex,w;
}edge[T<<1];
int head[T],cnt = 0;
void add(int u,int v,int w) {
    cnt++;
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}
int n,m,b;
int mon[T];

int d[T],vis[T];
void dij(int s,int xian) {
    memset(d,63,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>> >q;
    q.push(make_pair(0,s));
    int last,lin,dd;
    while(q.size()) {
        last = q.top().second;
        q.pop();
        if(vis[last]) continue;
        vis[last] = 1;
        for(int i = head[last];i;i = edge[i].nex) {
        if(mon[lin] > xian) continue;//33行
            lin = edge[i].to,dd = edge[i].w;//34行
            if(d[lin] > d[last]+dd) {
                d[lin] = d[last]+dd;
                q.push(make_pair(d[lin],lin));
            }
        }
    }
}

int mmm[T];

signed main() {
    scanf("%lld%lld%lld",&n,&m,&b);
    for(int i = 1;i <= n;mmm[i] = mon[i],i++)
        scanf("%lld",&mon[i]);
    int u,v,w;
    for(int i = 1;i <= m;i++) {
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    sort(mmm+1,mmm+n+1);
    int ans = 0;
    for(int i = (1 << 14);i;i >>= 1) {
        if(ans+i <= n) {
            if(mmm[ans+i] < mon[1] || mmm[ans+i] < mon[n]) {
                ans += i;
                continue;
            }
            dij(1,mmm[ans+i]);
            if(d[n] > b)
                ans += i;
        }
    }
    ans++;
    if(ans > n) printf("AFK");
    else printf("%lld",mmm[ans]);
    return 0;
}

by _TG_ @ 2023-08-12 09:45:39

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

by Chinshyo @ 2023-08-13 23:50:13

@Wu1hong2shen3 能不能具体说一下赋啥值，判断啥

我这个代码A W T全有，不太懂为啥会错，能不能看看

https://www.luogu.com.cn/record/120741586

而且我代码开了O2会RE，不懂啥原因

#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(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 Wu1hong2shen3_why_42 @ 2023-08-14 07:17:39

@qxhAwA 我说的是将将34行的赋值移到33行前

by Wu1hong2shen3_why_42 @ 2023-08-14 07:24:02

@qxhAwA 目测优先队列没清空

by Wu1hong2shen3_why_42 @ 2023-08-14 07:24:20

@qxhAwA 还有几分钟就打学校模拟赛了，我等一下再看看

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

@Wu1hong2shen3 我队列空了才会停止循环呀，不会出现队列没清空的情况吧

by Chinshyo @ 2023-08-14 08:36:36

@Wu1hong2shen3 aa我好像知道哪里错了