이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
typedef int64_t i64;
const i64 INF = i64(1e18); //1000000007; //998244353;
struct S {
int n, m;
vector<unordered_map<i64, set<pair<i64, i64>>>> edges;
vector<unordered_map<i64, i64>> csum;
void run() {
cin >> n >> m;
edges.resize(n);
csum.resize(n);
for (int i = 0; i < m; ++i) {
i64 a, b, c, p;
cin >> a >> b >> c >> p;
--a; --b;
edges[a][c].insert({b, p});
edges[b][c].insert({a, p});
csum[a][c] += p;
csum[b][c] += p;
}
vector<i64> d(n, INF);
vector<unordered_map<i64, i64>> d2(n);
d[0] = 0;
priority_queue<array<i64, 3>> q;
q.push({0, 0, 0});
while (!q.empty()) {
PAR(q.top());
i64 dist = -q.top()[0];
i64 node = q.top()[1];
i64 c = q.top()[2];
q.pop();
if (c) {
if (d2[node][c] != dist) continue;
for (auto [next, wt] : edges[node][c]) {
i64 rest = d2[node][c] + csum[node][c] - wt;
if (rest < d[next]) {
d[next] = rest;
q.push({-rest, next, 0});
}
}
} else {
if (d[node] != dist) continue;
for (auto &[color, adj] : edges[node]) {
for (auto [next, wt] : adj) {
i64 rest = d[node] + csum[node][color] - wt;
if (rest < d[next]) {
d[next] = rest;
q.push({-rest, next, 0});
}
if (d[node] + wt < d[next]) {
d[next] = d[node] + wt;
q.push({-d[node] - wt, next, 0});
}
if (!d2[next].count(color) || dist < d2[next][color]) {
d2[next][color] = dist;
q.push({-dist, next, color});
}
}
}
}
}
cout << (d[n - 1] >= INF ? -1 : d[n - 1]) << '\n';
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
auto sol = make_unique<S>();
sol->run();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |