二分答案,用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;
}