제출 #771243

#제출 시각아이디문제언어결과실행 시간메모리
771243SamNguyenRobot (JOI21_ho_t4)C++14
34 / 100
3082 ms27144 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; } template <class T1, class T2> inline constexpr bool maximise(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); } } lli dist[MAX_N]; min_priority_queue<pair<lli, int>> pq; lli sum_by_colour[MAX_M], min_by_colour[MAX_M]; lli solve() { memset(dist, 0x1f, sizeof dist); memset(sum_by_colour, 0, sizeof sum_by_colour); memset(min_by_colour, 0x1f, sizeof min_by_colour); auto relax = [&](int u, lli d) { if (minimise(dist[u], d)) pq.emplace(d, u); }; relax(1, 0); lli ans = INF; while (not pq.empty()) { lli cur_dist; int u; tie(cur_dist, u) = pq.top(); pq.pop(); if (u == N) minimise(ans, cur_dist); cerr << "dist " << u << " = " << dist[u] << endl; if (cur_dist > dist[u]) continue; for (int j : adj[u]) { int v = edge[j].other_node(u); int c = edge[j].colour(); lli w = edge[j].cost(); sum_by_colour[c] += w; minimise(min_by_colour[c], dist[v]); cerr << "j = " << j << " -> (" << u << ", " << edge[j].other_node(u) << ")" << endl; } for (int j : adj[u]) { int v = edge[j].other_node(u); int c = edge[j].colour(); lli w = edge[j].cost(); relax(v, cur_dist + min(w, sum_by_colour[c] - w)); relax(v, min_by_colour[c] + sum_by_colour[c] - w); } for (int j : adj[u]) { int c = edge[j].colour(); sum_by_colour[c] = 0; min_by_colour[c] = INF; } } if (ans >= INF) ans = -1; return ans; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); input(); cout << solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...