제출 #415897

#제출 시각아이디문제언어결과실행 시간메모리
415897egod1537Robot (JOI21_ho_t4)C++14
58 / 100
3075 ms109180 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<int> tidx; vector<vector<int>> vidx; vector<map<int, int>> cidx; 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); cidx.resize(n + 1); colcnt.resize(n + 1); colsum.resize(n + 1); vcole.resize(n + 1); vidx.resize(n + 1); tidx.resize(n + 1); cidx.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; if (cidx[from].find(col) == cidx[from].end()) { vidx[from].push_back(vnum++); cidx[from][col] = tidx[from]++; vcole[from].push_back(vector<Line>()); colcnt[from].push_back(0); colsum[from].push_back(0); } if (cidx[to].find(col) == cidx[to].end()) { vidx[to].push_back(vnum++); cidx[to][col] = tidx[to]++; vcole[to].push_back(vector<Line>()); colcnt[to].push_back(0); colsum[to].push_back(0); } int fromc = cidx[from][col], toc = cidx[to][col]; colcnt[from][fromc]++, colsum[from][fromc] += cost; colcnt[to][toc]++, colsum[to][toc] += cost; vcole[from][fromc].push_back({ to, col, cost }); vcole[to][toc].push_back({ from, col, cost }); V[from].push_back({ to, col, cost, fromc }); V[to].push_back({ from, col, cost, toc }); } 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 = cidx[w.to][w.col]; V[i].push_back({ vidx[w.to][idx], w.col, 0, idx }); } for (auto& p : cidx[i]) { int col = p.first, idx = p.second; for (Line& w : vcole[i][idx]) V[vidx[i][idx]].push_back({ w.to, w.col, colsum[i][idx] - w.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; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:78:8: warning: unused variable 'col' [-Wunused-variable]
   78 |    int col = p.first, idx = p.second;
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...