P1462求助
  • 板块题目总版
  • 楼主WD2c0mP
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/20 08:58
  • 上次更新2024/7/20 10:10:21
查看原帖
P1462求助
780641
WD2c0mP楼主2024/7/20 08:58

二分答案,用Dijkstra求当前情况(无法到达点权大于mid的点)下的最短路是否小于b
为什么Dijkstra这部分求出来的最短路都是0???

#include<bits/stdc++.h>
using namespace std;
int n,m,b,r;
int f[10010],dis[10010],vis[10010];
vector<pair<int,int> >G[10010]; // 反过来存 
bool check(int mid) {
    memset(dis,0,sizeof(dis));
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; // first是距离 second是 dian 
    dis[1] = 0;
    q.push({0,1});
    while (!q.empty()) {
        pair<int,int> u = q.top();
        q.pop();
        int x = u.second;
        if (f[x] > mid || vis[x]) continue;
        vis[x] = 1;
        for (unsigned i = 0;i < G[x].size();i ++) {
            int y = G[x][i].second;
            if (dis[y] > dis[x] + G[x][i].first) {
                dis[y] = dis[x] + G[x][i].first;
                if (!vis[y]) q.push({dis[y],y});
            }
        }
    }
    //cout << mid << " " << dis[n] << endl;
    if (dis[n] != 0 && dis[n] < b) return true;
    return false; 
}
int main() {
    cin >> n >> m >> b;
    for (int i = 1;i <= n;i ++) cin >> f[i],r = max(r,f[i]);
    for (int i = 1;i <= m;i ++) {
        int u,v,w;
        cin >> u >> v >> w;
        G[u].push_back({w,v});
        G[v].push_back({w,u});
    }
    int l = 1,mid,ret = -360;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1,ret = mid;
        else l = mid + 1;
    }
    if (ret != -360) cout << ret << endl;
    else cout << "AFK" << endl;
    return 0;
}
2024/7/20 08:58
加载中...