제출 #771048

#제출 시각아이디문제언어결과실행 시간메모리
771048SamNguyenRobot (JOI21_ho_t4)C++14
0 / 100
3044 ms29436 KiB
#include <bits/stdc++.h> using namespace std; using lli = long long; template <class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; const lli INF = 0x1f1f1f1f1f1f1f1f; const int MAX_N = 1e5 + 7; const int MAX_M = 2e5 + 7; template <class T1, class T2> inline constexpr bool minimise(T1 &x, T2 y) { if (x > y) { x = y; return true; } return false; } class Edge { private: int u, v, c; lli w; public: Edge(int u = 0, int v = 0, int c = 0, lli w = 0): u(u), v(v), c(c), w(w) {} inline lli cost() const { return w; } inline pair<int, int> nodes() const { return make_pair(u, v); } inline int other_node(int z) const { return u ^ v ^ z; } inline int colour() const { return c; } inline int get_node(bool is_rev) const { return is_rev ? v : u; } inline bool is_start(int z) const { return z == u; } }; int N, M; Edge edge[MAX_M]; vector<int> adj[MAX_N]; void input() { cin >> N >> M; for (int i = 0; i < M; i++) { int u, v, c; lli w; cin >> u >> v >> c >> w; edge[i] = Edge(u, v, c, w); adj[u].push_back(i); adj[v].push_back(i); } edge[M] = Edge(0, 1, M + 1, 0); } lli dist[MAX_M][2][2]; min_priority_queue<tuple<lli, int, bool, bool>> pq; int cnt_colour[MAX_M]; lli solve() { memset(dist, 0x1f, sizeof dist); memset(cnt_colour, 0, sizeof cnt_colour); auto relax = [&](int i, bool is_rev, bool is_prev_mod, lli d) { if (minimise(dist[i][is_rev][is_prev_mod], d)) pq.emplace(d, i, is_rev, is_prev_mod); }; relax(M, 0, 0, 0); while (not pq.empty()) { lli cur_dist; int i; bool is_rev, is_prev_mod; tie(cur_dist, i, is_rev, is_prev_mod) = pq.top(); pq.pop(); { int u, v; tie(u, v) = edge[i].nodes(); if (is_rev) swap(u, v); cerr << "edge (" << u << "," << v << "), is_prev_mod = " << is_prev_mod << " ==> " << cur_dist << endl; } int v = edge[i].get_node(not is_rev); if (v == N) return cur_dist; for (int j : adj[v]) { int c = edge[j].colour(); cerr << j << "(" << c << ") "; if (j == i and not is_prev_mod) continue; cnt_colour[c]++; } cerr << endl; for (int j : adj[v]) { int c = edge[j].colour(); if (cnt_colour[c] <= 1) relax(j, not edge[j].is_start(v), false, cur_dist); relax(j, not edge[j].is_start(v), true, cur_dist + edge[j].cost()); } for (int j : adj[v]) { int c = edge[j].colour(); cnt_colour[c] = 0; } } return -1; } int main(void) { input(); cout << solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...