제출 #1109545

#제출 시각아이디문제언어결과실행 시간메모리
1109545nh0902Robot (JOI21_ho_t4)C++14
34 / 100
3063 ms63028 KiB
#include <bits/stdc++.h> using namespace std; const int N = 110000; long long const inf = 1e18; 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; }; 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}); while (!pq.empty()) { Node t = pq.top(); pq.pop(); if (t.c > 0) { if (t.d > D[t.x][t.c]) continue; for (Edge e : v[t.x]) { if (e.c == t.c) { long long next_d = t.d + ma[t.x][t.c] - e.p; if (dp[e.a] > next_d) { dp[e.a] = next_d; pq.push({e.a, dp[e.a], 0}); } } } } else { for (Edge e : v[t.x]) { if (D[e.a][e.c] > t.d) { D[e.a][e.c] = t.d; pq.push({e.a, t.d, e.c}); } long long next_d = ma[t.x][e.c] - e.p + t.d; if (dp[e.a] > next_d) { dp[e.a] = next_d; pq.push({e.a, next_d, 0}); } next_d = t.d + e.p; if (dp[e.a] > next_d) { dp[e.a] = next_d; pq.push({e.a, next_d, 0}); } } } } if (dp[n] > inf / 2) { cout << -1; return 0; } cout << dp[n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...