제출 #415900

#제출 시각아이디문제언어결과실행 시간메모리
415900egod1537Robot (JOI21_ho_t4)C++14
58 / 100
3065 ms91436 KiB
#include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; struct Line { int to, col; ll cost; int cc; }; struct Q { int pos; ll cost; }; bool operator<(const Q& a, const Q& b) { return a.cost > b.cost; } vector<vector<Line>> V; vector<vector<int>> vc; vector<vector<int>> vidx; vector<vector<vector<Line>>> vcole; vector<vector<int>> colcnt; vector<vector<ll>> colsum; vector<ll> dst; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; V.resize(n + 1); colcnt.resize(n + 1); colsum.resize(n + 1); vcole.resize(n + 1); vidx.resize(n + 1); vc.resize(n + 1); int vnum = n + 1; for (int i = 0; i < m; i++) { int from, to, col; ll cost; cin >> from >> to >> col >> cost; vc[from].push_back(col); vc[to].push_back(col); V[from].push_back({ to, col, cost }); V[to].push_back({ from, col, cost }); } for (int i = 1; i <= n; i++) { vector<int>& v = vc[i]; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int sz = v.size(); vidx[i].resize(sz); colcnt[i].resize(sz); colsum[i].resize(sz); vcole[i].resize(sz); for (int& w : vidx[i]) w = vnum++; for (Line& w : V[i]) { int fromc = lower_bound(v.begin(), v.end(), w.col) - v.begin(); colcnt[i][fromc]++; colsum[i][fromc] += w.cost; vcole[i][fromc].push_back(w); w.cc = fromc; } } dst.resize(vnum + 1, 1e18); for (int i = n + 1; i < vnum; i++) V.push_back(vector<Line>()); for (int i = 1; i <= n; i++) { int sz = V[i].size(); for (int j = 0; j < sz; j++) { Line& w = V[i][j]; int idx = lower_bound(vc[w.to].begin(), vc[w.to].end(), w.col) - vc[w.to].begin(); V[i].push_back({ vidx[w.to][idx], w.col, 0, idx }); } for (int w : vc[i]) { int col = w, idx = lower_bound(vc[i].begin(), vc[i].end(), col) - vc[i].begin(); if (colcnt[i][idx] <= 1) continue; for (Line& l : vcole[i][idx]) V[vidx[i][idx]].push_back({ l.to, l.col, colsum[i][idx] - l.cost, idx }); } } priority_queue<Q> pq; pq.push({ 1, 0 }); dst[1] = 0; while (!pq.empty()) { Q top = pq.top(); pq.pop(); if (top.pos == n) break; for (Line& w : V[top.pos]) { ll& ret = dst[w.to]; if (top.pos <= n) { if (w.to > n) { if (ret > top.cost) { ret = top.cost; pq.push({ w.to, ret }); } } else { int idx = w.cc; if (colcnt[top.pos][idx] == 1) { if (ret > top.cost) { ret = top.cost; pq.push({ w.to, ret }); } } else { if (ret > top.cost + w.cost) { ret = top.cost + w.cost; pq.push({ w.to, ret }); } if (ret > top.cost + colsum[top.pos][idx] - w.cost) { ret = top.cost + colsum[top.pos][idx] - w.cost; pq.push({ w.to, ret }); } } } } else { if (ret > top.cost + w.cost) { ret = top.cost + w.cost; pq.push({ w.to, ret }); } } } } cout << (dst[n] == 1e18 ? -1 : dst[n]) << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...