1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 10000; const int INF = 2147483647; int n, m, b; // 城市数量,公路数量,血量 int f[MAXN + 5]; // 每个城市过路费 // 存图 <终点,血量花费> vector<pair<int, int>> e[MAXN + 5]; // 检查花费最大值小于等于 mid 时能否达成 int dis[MAXN + 5]; // 最少花费血量 bool vis[MAXN + 5]; // <花费血量,城市编号> priority_queue<pair<int, int>> pq; bool check(int mid) { if (f[1] > mid) return false; for (int i = 1; i <= n; i++) { dis[i] = INF; vis[i] = false; } dis[1] = 0; pq.push(make_pair(-0, 1)); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].first; int w = e[u][i].second; if (f[v] <= mid && dis[u] + w < dis[v]) { dis[v] = dis[u] + w; pq.push(make_pair(-dis[v], v)); } } } return dis[n] <= b; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> b; for (int i = 1; i <= n; i++) cin >> f[i]; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; e[u].push_back(make_pair(v, w)); e[v].push_back(make_pair(u, w)); } // 二分限制花费的最大值 int l = 0; int r = 1'000'000'000; int ans = -1; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } if (ans == -1) cout << "AFK"; else cout << ans; return 0; }
- 1
信息
- ID
- 1830
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 52
- 已通过
- 7
- 上传者