This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
int max_score(int N, int X, int Y, long long K,vector<int> U, vector<int> V, vector<int> W) {
vector<vector<array<int, 2>>> adj(N);
for (int i = 0; i < N; i++ ) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
vector<long long> d;
vector<long long> dx(N, 1e9); dx[X] = 0;
priority_queue<pair<long long, int>> pq; pq.push({0, X});
while (!pq.empty()) {
int a = pq.top().second; pq.pop();
for (auto x : adj[a]) {
if (dx[x[0]] > dx[a]+x[1]) {
dx[x[0]] = dx[a]+x[1];
pq.push({-dx[x[0]], x[0]});
}
}
}
vector<long long> dy(N, 1e9); dy[Y] = 0;
pq.push({0, Y});
while (!pq.empty()) {
int a = pq.top().second; pq.pop();
for (auto x : adj[a]) {
if (dy[x[0]] > dy[a]+x[1]) {
dy[x[0]] = dy[a]+x[1];
pq.push({-dy[x[0]], x[0]});
}
}
}
for (int i = 0; i < N; i++) {
d.push_back(dx[i]); d.push_back(dy[i]);
}
sort(d.begin(), d.end());
long long att = 0, k = 0;
while (att+d[k] <= K) {
att += d[k]; k++;
}
return k;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |