QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#364693#8136. Rebellious Edgechengning0909WA 37ms20908kbC++171.6kb2024-03-24 16:06:142024-03-24 16:06:15

Judging History

你现在查看的是最新测评结果

  • [2024-03-24 16:06:15]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:20908kb
  • [2024-03-24 16:06:14]
  • 提交

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'