제출 #500279

#제출 시각아이디문제언어결과실행 시간메모리
500279couplefireRobot (JOI21_ho_t4)C++17
100 / 100
163 ms20332 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair using namespace std; struct edge { int v,c,cost; edge(){} edge(int _v, int _c, int _cost) { v = _v; c = _c; cost = _cost; } }; const int N = 1e5 + 5; const int M = 2e5 + 5; const long long oo = 1e18; vector <edge> adj[N]; long long dis[2 * N]; long long sum[M]; long long best[M]; int n,m; template <typename T> bool mini(T &a, T b) { if (a > b) { a = b; return true; } return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { int u,v,c,w; cin >> u >> v >> c >> w; edge a = edge(v, c, w); edge b = edge(u, c, w); adj[u].push_back(a); adj[v].push_back(b); } for (int i = 1; i <= n; i++) dis[i] = oo; for (int i = 1; i <= m; i++) best[i] = oo; dis[1] = 0; priority_queue <pair <long long, int>> heap; heap.push(mp(0, 1)); while (heap.size()) { int u = heap.top().se; long long cur = -heap.top().fi; heap.pop(); if (cur != dis[u]) continue; for (edge e : adj[u]) { sum[e.c] += e.cost; best[e.c] = min(best[e.c], dis[e.v]); } for (edge e : adj[u]) { int v = e.v; int c = e.c; int w = e.cost; long long tmp = min(0LL + w, sum[c] - w); if (mini(dis[v], cur + tmp)) heap.push(mp(-dis[v], v)); if (mini(dis[v], best[c] + sum[c] - w)) heap.push(mp(-dis[v], v)); } for (edge e : adj[u]) { sum[e.c] = 0; best[e.c] = oo; } } if (dis[n] == oo) dis[n] = -1; cout << dis[n]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...