제출 #734258

#제출 시각아이디문제언어결과실행 시간메모리
734258asdfgraceRobot (JOI21_ho_t4)C++17
100 / 100
830 ms119736 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...