QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#631989 | #5579. Bog of Eternal Stench | enze114514 | TL | 0ms | 0kb | C++20 | 1.3kb | 2024-10-12 11:20:20 | 2024-10-12 11:20:21 |
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);
vector<bool> in_queue(n + 1, false);
vector<int> cnt(n + 1, 0); // Count of relaxations for negative cycle detection (not needed here)
stench[1] = 0;
queue<int> q;
q.push(1);
in_queue[1] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (auto &[v, s_uv] : adj[u]) {
ll s_v_candidate = max(0LL, stench[u] + s_uv);
if (s_v_candidate < stench[v]) {
stench[v] = s_v_candidate;
if (!in_queue[v]) {
q.push(v);
in_queue[v] = true;
// cnt[v]++;
// Optional negative cycle detection, but not necessary here
}
}
}
}
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...