QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#664932 | #5579. Bog of Eternal Stench | enze114514 | WA | 1ms | 3616kb | C++20 | 1.5kb | 2024-10-21 23:37:29 | 2024-10-21 23:37:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ld pi = 3.14159265358979323846;
const ll INF = 1e18;
const int mod = (int)1e9 + 7;
template<typename T>
T chmax(T a, T b) {
return a > b ? a : b;
}
template<typename T>
T chmin(T a, T b) {
return a > b ? b : a;
}
const int N = 3e3 + 1, M = N * 2;
void solve() {
int n, m;
cin >> n >> m;
const ll INF = 1e18;
vector<vector<pair<int, ll>>> adj(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
vector<ll> f(n + 1, INF);
vector<int> vs(n + 1, 0);
f[1] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> q;
q.push({0, 1});
while (!q.empty()) {
auto p = q.top();
q.pop();
int u = p.second;
if(vs[u] > 1){
continue;
}
vs[u]++;
for(auto g : adj[u]){
int v = g.first, w = g.second;
if(f[v] > f[u] + w){
f[v] = (w < 0 ? 0 : chmax(0ll, f[u] + w));
q.push({f[v], v});
}
}
}
cout << f[n] << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
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...
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
4 4 1 2 5 1 3 -2 2 4 1 3 4 10
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
5 5 1 2 1000 2 3 -3 3 4 1 4 2 0 2 5 2
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
3 3 1 3 -10 3 2 2 2 3 -1
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
2 1 1 2 0
output:
0
result:
ok single line: '0'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3612kb
input:
6 6 1 2 1000000000 2 6 -1 3 2 0 4 3 -1 3 5 -1 5 4 -1
output:
0
result:
wrong answer 1st lines differ - expected: '999999999', found: '0'