제출 #1109406

#제출 시각아이디문제언어결과실행 시간메모리
1109406nh0902Robot (JOI21_ho_t4)C++14
0 / 100
104 ms30156 KiB
#include <bits/stdc++.h> using namespace std; const int N = 110000; long long const inf = 1e16; int n, m; struct Edge { int a, c; long long p; }; vector<Edge> v[N]; map<int, long long> ma[N]; long long dp[N]; map<int, long long> D[N]; struct Node { int x; long long d; int c; long long p; int pa; }; struct cmp{ bool operator() (Node u, Node v) { return u.d > v.d; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; int a, b, c; long long p; for (int i = 1; i <= m; i ++) { cin >> a >> b >> c >> p; v[a].push_back({b, c, p}); v[b].push_back({a, c, p}); } for (int i = 1; i <= n; i ++) { for (Edge e : v[i]) { if (ma[i].find(e.c) == ma[i].end()) { ma[i][e.c] = 0; } ma[i][e.c] += e.p; } } priority_queue<Node, vector<Node>, cmp> pq; for (int i = 1; i <= n; i ++) { for (Edge e : v[i]) { D[i][e.c] = inf; } dp[i] = inf; } dp[1] = 0; pq.push({1, 0, 0, 0, 0}); while (!pq.empty()) { Node t = pq.top(); pq.pop(); if (t.d > D[t.x][t.c]) continue; for (Edge e : v[t.x]) { if (D[e.a][e.c] > t.d + e.p) { D[e.a][e.c] = t.d + e.p; pq.push({e.a, t.d + e.p, e.c, e.p, t.x}); } if (e.c == t.c) { if (e.a != t.pa) { long long next_d = t.d + ma[t.x][e.c] - e.p - t.p; if (dp[e.a] > next_d) { dp[e.a] = next_d; pq.push({e.a, next_d, 0, 0, t.x}); } } } else { long long next_d = t.d + ma[t.x][e.c] - e.p; if (dp[e.a] > next_d) { dp[e.a] = next_d; pq.push({e.a, next_d, 0, 0, t.x}); } } } } long long ans = inf; for (auto d : D[n]) { ans = min(ans, d.second); } if (ans == inf) { cout << -1; return 0; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...