QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#631985 | #5579. Bog of Eternal Stench | enze114514 | TL | 0ms | 0kb | C++20 | 1.2kb | 2024-10-12 11:18:45 | 2024-10-12 11:18:45 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, m;
cin >> n >> m;
const ll INF = 1e18;
vector<vector<pair<int, ll>>> adj(n + 1); // Adjacency list: (neighbor, stench change)
for (int i = 0; i < m; ++i) {
int u, v;
ll s;
cin >> u >> v >> s;
adj[u].emplace_back(v, s);
}
vector<ll> stench(n + 1, INF);
stench[1] = 0;
// Priority queue: (stench level, node)
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
pq.emplace(0, 1);
while (!pq.empty()) {
auto [s_u, u] = pq.top();
pq.pop();
// If we have already found a better stench level, skip
if (s_u > stench[u]) continue;
for (auto &[v, s_uv] : adj[u]) {
ll s_v_candidate = max(0LL, s_u + s_uv);
if (s_v_candidate < stench[v]) {
stench[v] = s_v_candidate;
pq.emplace(stench[v], v);
}
}
}
cout << stench[n] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
1999 1999 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 10 11 1000000000 11 12 1000000000 12 13 1000000000 13 14 1000000000 14 15 1000000000 15 16 1000000000 16 17 1000000000 17 18 1000000000 18 19 1000000000 1...