제출 #686534

#제출 시각아이디문제언어결과실행 시간메모리
686534etheningRobot (JOI21_ho_t4)C++17
58 / 100
3082 ms150712 KiB
#include "bits/stdc++.h" #include <queue> #include <unordered_map> using namespace std; using ll = long long; #define DEBUG 0 const ll INF = 1000'000'000'000'000'000ll; const int MAXN = 100000; const int MAXM = 200000; int n, m; unordered_map<int, int> s[MAXN + 5]; unordered_map<int, ll> csum[MAXN + 5]; int a[MAXM + 5][4]; struct edge { int fr; int to; ll weight; } e[10 * MAXM + 5]; vector<int> v[10 * MAXM + 5]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; int cnt = 0; s[1][0] = ++cnt; s[n][0] = ++cnt; int ecnt = 0; for (int i = 1; i <= m; i++) { cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3]; if (s[a[i][0]].find(0) == s[a[i][0]].end()) { s[a[i][0]][0] = ++cnt; } if (s[a[i][0]].find(a[i][2]) == s[a[i][0]].end()) { s[a[i][0]][a[i][2]] = ++cnt; e[++ecnt] = {.fr = s[a[i][0]][0], .to = cnt, .weight = 0}; v[s[a[i][0]][0]].push_back(ecnt); } if (csum[a[i][0]].find(a[i][2]) == csum[a[i][0]].end()) { csum[a[i][0]][a[i][2]] = a[i][3]; } else csum[a[i][0]][a[i][2]] += a[i][3]; if (s[a[i][1]].find(0) == s[a[i][1]].end()) { s[a[i][1]][0] = ++cnt; } if (s[a[i][1]].find(a[i][2]) == s[a[i][1]].end()) { s[a[i][1]][a[i][2]] = ++cnt; e[++ecnt] = {.fr = s[a[i][1]][0], .to = cnt, .weight = 0}; v[s[a[i][1]][0]].push_back(ecnt); } if (csum[a[i][1]].find(a[i][2]) == csum[a[i][1]].end()) { csum[a[i][1]][a[i][2]] = a[i][3]; } else csum[a[i][1]][a[i][2]] += a[i][3]; } if (DEBUG) { for (int i = 1; i <= n; i++) { for (auto [dex, val] : s[i]) { cout << "i: " << i << " col: " << dex << " index: " << val << endl; } } } for (int i = 1; i <= m; i++) { int col = a[i][2]; int fr = a[i][0]; int to = a[i][1]; int node10 = s[fr][0]; int node1c = s[fr][col]; int node20 = s[to][0]; int node2c = s[to][col]; e[++ecnt] = {.fr = node10, .to = node20, .weight = (ll)a[i][3]}; v[node10].push_back(ecnt); e[++ecnt] = {.fr = node20, .to = node10, .weight = (ll)a[i][3]}; v[node20].push_back(ecnt); e[++ecnt] = {.fr = node10, .to = node2c, .weight = 0}; v[node10].push_back(ecnt); e[++ecnt] = {.fr = node20, .to = node1c, .weight = 0}; v[node20].push_back(ecnt); e[++ecnt] = {.fr = node1c, .to = node20, .weight = csum[fr][col] - a[i][3]}; v[node1c].push_back(ecnt); e[++ecnt] = {.fr = node2c, .to = node10, .weight = csum[to][col] - a[i][3]}; v[node2c].push_back(ecnt); if (DEBUG) cout << ecnt << endl; } if (DEBUG) { for (int i = 1; i <= ecnt; i++) { cout << "fr: " << e[i].fr << " to: " << e[i].to << " we: " << e[i].weight << endl; } } int source = s[1][0]; int dest = s[n][0]; vector<ll> dist(cnt + 5, INF); typedef pair<ll, int> pli; priority_queue<pli, vector<pli>, greater<pli>> Q; dist[source] = 0; Q.push({0, source}); while (!Q.empty()) { auto [curDist, cur] = Q.top(); Q.pop(); if (dist[cur] > curDist) continue; if (cur == dest) break; for (auto eg: v[cur]) { if (dist[cur] + e[eg].weight < dist[e[eg].to]) { dist[e[eg].to] = dist[cur] + e[eg].weight; Q.push({dist[e[eg].to], e[eg].to}); } } } if (DEBUG) { for (int i = 1; i <= cnt; i++) { cout << "dist " << i << " : " << dist[i] << endl; } } if (DEBUG) { cout << "DEST: " << dest << endl; } if (dist[dest] == INF) dist[dest] = -1; cout << dist[dest] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...