QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#581085 | #8136. Rebellious Edge | ucup-team1766# | WA | 0ms | 3536kb | C++17 | 2.5kb | 2024-09-22 07:22:02 | 2024-09-22 07:22:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct Step {
int to;
long long d;
Step(int t, long long dd) : to(t), d(dd) {}
bool operator<(const Step &o) const {
return d > o.d;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> graph(n);
vector<int> min_in(n, INT_MAX);
int start, end, wb;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--; v--;
if (u < v) {
graph[u].emplace_back(v, w);
min_in[v] = min(min_in[v], w);
} else {
start = u;
end = v;
wb = w;
}
}
vector<long long> psum(n);
for (int i = 1; i < n; i++) {
psum[i] = psum[i - 1] + (min_in[i] == INT_MAX ? 0 : min_in[i]);
}
long long mst1 = 0;
bool mst1_possible = true;
for (int i = 1; i < n; i++) {
if (min_in[i] == INT_MAX) {
mst1_possible = false;
break;
}
mst1 += min_in[i];
}
long long after_cost = 0;
for (int i = start + 1; i < n; i++) {
after_cost += min_in[i];
}
bool mst2_possible = (end > 0);
long long mst2 = wb;
if (mst2_possible) {
vector<vector<pair<int, long long>>> g2(n);
for (int i = 0; i < n; i++) {
for (auto [to, w] : graph[i]) {
if (to != start) {
g2[i].emplace_back(to, w + psum[to - 1] - psum[i]);
}
}
}
vector<long long> dists(n, LONG_LONG_MAX);
priority_queue<Step> pq;
pq.emplace(0, 0);
while (!pq.empty()) {
Step cur = pq.top();
pq.pop();
if (cur.d >= dists[cur.to]) {
continue;
}
dists[cur.to] = cur.d;
for (auto [nei, w] : g2[cur.to]) {
if (nei <= start) {
pq.emplace(nei, cur.d + w);
}
}
}
if (dists[start] < LONG_LONG_MAX) {
mst2 = dists[start] + after_cost;
} else {
mst2_possible = false;
}
}
long long res = mst1;
if (!mst1_possible || (mst2_possible && mst2 < mst1)) {
res = mst2;
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3536kb
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:
6 18 1100
result:
wrong answer 1st numbers differ - expected: '5', found: '6'