Submission #416014

#TimeUsernameProblemLanguageResultExecution timeMemory
416014meatrowRobot (JOI21_ho_t4)C++17
0 / 100
3078 ms62180 KiB
// #pragma GCC target ("avx2") // #pragma GCC optimization ("O3") #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int MOD = 1e9 + 7; ll binpow(ll a, ll p, int mod = MOD) { ll res = 1; while (p) { if (p & 1) { (res *= a) %= mod; } p >>= 1; (a *= a) %= mod; } return res; } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } struct Edge { int a, b, color, price; }; void solve() { int n, m; cin >> n >> m; vector<Edge> edges(m); vector<vector<int>> g(n + 1); vector<map<int, int>> rev(n + 1); for (int i = 0; i < m; i++) { cin >> edges[i].a >> edges[i].b >> edges[i].color >> edges[i].price; g[edges[i].a].push_back(i); g[edges[i].b].push_back(i); rev[edges[i].a][i] = g[edges[i].a].size() - 1; rev[edges[i].b][i] = g[edges[i].b].size() - 1; } vector<vector<ll>> dist(n + 1); for (int i = 1; i <= n; i++) { dist[i].assign(g[i].size() * 2 + 1, 1e18); } dist[1][0] = 0; set<pair<ll, pair<int, int>>> setik; setik.insert({0, {1, 0}}); while (!setik.empty()) { int v, from; tie(v, from) = setik.begin()->second; setik.erase(setik.begin()); map<int, ll> sum; for (int i = 0; i < g[v].size(); i++) { auto& edge = edges[g[v][i]]; if (from != i * 2 + 1) { sum[edge.color] += edge.price; } } for (int i = 0; i < g[v].size(); i++) { if (from == i * 2 + 1) continue; auto& edge = edges[g[v][i]]; int to = edge.a ^ edge.b ^ v; int w = edge.price; int id = rev[to][g[v][i]]; if (dist[v][from] + w < dist[to][id * 2 + 1]) { setik.erase({dist[to][id * 2 + 1], {to, id * 2 + 1}}); dist[to][id * 2 + 1] = dist[v][from] + w; setik.insert({dist[to][id * 2 + 1], {to, id * 2 + 1}}); } w = sum[edge.color] - edge.price; if (dist[v][from] + w < dist[to][id * 2]) { setik.erase({dist[to][id * 2], {to, id * 2}}); dist[to][id * 2] = dist[v][from] + w; setik.insert({dist[to][id * 2], {to, id * 2}}); } } } ll ans = *min_element(dist[n].begin(), dist[n].end()); if (ans == 1e18) ans = -1; cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; for (int tc = 1; tc <= T; tc++) { // cout << "Case #" << tc << ": "; solve(); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int i = 0; i < g[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i = 0; i < g[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...