Submission #1081505

#TimeUsernameProblemLanguageResultExecution timeMemory
1081505PanndaRobot (JOI21_ho_t4)C++17
0 / 100
219 ms67132 KiB
#include <bits/stdc++.h> using namespace std; template <class T> vector<T> dijkstra(const vector<vector<pair<int, T>>> &adj, vector<T> dist) { int n = adj.size(); priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq; for (int u = 0; u < n; u++) { pq.push({dist[u], u}); } while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; struct Edge { int v, color, cost; }; vector<vector<Edge>> edges(n); vector<vector<int>> colors(n); for (int i = 0; i < m; i++) { int u, v, color, cost; cin >> u >> v >> color >> cost; u--; v--; edges[u].push_back({v, color, cost}); edges[v].push_back({u, color, cost}); colors[u].push_back(color); colors[v].push_back(color); } for (int u = 0; u < n; u++) { sort(colors[u].begin(), colors[u].end()); colors[u].resize(unique(colors[u].begin(), colors[u].end()) - colors[u].begin()); } auto f = [&](int u, int color) -> int { int i = lower_bound(colors[u].begin(), colors[u].end(), color) - colors[u].begin(); assert(i < colors[u].size()); return i; }; vector<vector<long long>> sum(n); vector<vector<int>> id(n); int tim = n; for (int u = 0; u < n; u++) { sum[u].resize(colors[u].size(), 0); for (auto [v, color, cost] : edges[u]) { sum[u][f(u, color)] += cost; } id[u].resize(colors[u].size()); iota(id[u].begin(), id[u].end(), tim); tim += colors[u].size(); } vector<vector<pair<int, long long>>> adj(tim); for (int u = 0; u < n; u++) { for (auto [v, color, cost] : edges[u]) { int i = f(u, color); adj[u].push_back({v, cost}); adj[u].push_back({v, sum[u][i] - cost}); // (u) -> (v) + cost; // (u) -> (v) + sum[f(u, color)][i] - cost // (u) -> (v, color) + 0 // (u, color) -> (v) + sum[u][f(u, color)] - cost } } const long long INF = 4e18; vector<long long> dist(tim, INF); dist[0] = 0; dist = dijkstra(adj, dist); cout << dist[n - 1] << '\n'; }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In lambda function:
Main.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         assert(i < colors[u].size());
      |                ~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...