QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#364693 | #8136. Rebellious Edge | chengning0909 | WA | 37ms | 20908kb | C++17 | 1.6kb | 2024-03-24 16:06:14 | 2024-03-24 16:06:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 5e5 + 10;
struct Node {
int u, v, w;
} e[N];
struct Edge {
int id, v, w;
};
int T, n, m, to[N], cnt[N];
vector<Edge> g[N];
vector<pii> G;
void Solve() {
cin >> n >> m;
int p;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
if (u < v) {
g[v].push_back({i, u, w});
} else p = i;
e[i] = {u, v, w};
if (u == 1) G.push_back({v, w});
}
ll ans = 0;
for (int i = 2; i <= n; i++) {
int mmin = 1e9 + 1, id;
for (Edge j : g[i]) if (mmin > j.w || (mmin == j.w && j.v == 1)) mmin = j.w, id = j.id;
ans += (mmin == 1e9 + 1 ? 0 : mmin), cnt[e[id].u]++, to[i] = id;
}
if (e[p].v != 1) {
ll sum = ans - e[to[e[p].v]].w + e[p].w;
if (g[e[p].v].empty()) ans = 1e18;
if (cnt[1] == 1 && e[to[e[p].v]].u == 1) {
to[e[p].v] = p;
for (pii i : G) {
if (e[p].v == i.first) continue;
ll s = sum + i.second - e[to[i.first]].w;
ans = min(ans, s);
}
} else ans = min(ans, sum);
}
cout << ans << '\n';
for (int i = 1; i <= n; i++) g[i].clear(), to[i] = cnt[i] = 0;
G.clear();
}
/*
1
3 2
3 2 0
1 3 1000000000
*/
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> T;
while (T--) Solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 20908kb
input:
3 5 6 1 2 4 1 3 2 2 3 0 3 4 1 4 5 1 5 2 1 4 4 1 2 4 1 3 6 1 4 8 4 2 1000000 3 3 1 2 100 2 1 10 2 3 1000
output:
5 18 1100
result:
ok 3 number(s): "5 18 1100"
Test #2:
score: -100
Wrong Answer
time: 37ms
memory: 19904kb
input:
50000 4 5 2 4 998973548 2 3 501271695 4 1 778395982 1 4 32454891 1 2 757288934 4 5 1 4 720856669 2 3 665098951 3 4 407461517 2 1 866914401 1 2 457859826 4 5 1 2 75288664 1 4 624893594 3 2 458973866 2 4 769074655 2 3 834773751 4 5 2 3 237060634 2 4 297307882 3 4 200383586 1 2 42856502 3 1 16574713 4 ...
output:
1291015520 1530420294 1534956009 480300722 1366795927 1077788279 2493849488 858095911 1034153425 793861088 605832428 1051598350 612891589 1265994009 517769091 1678219738 1556463491 93634961 960978736 984886788 1696503797 1002892611 1969660290 1431417780 1515267731 977157479 1937478556 654475526 1401...
result:
wrong answer 6th numbers differ - expected: '1541095843', found: '1077788279'