제출 #992542

#제출 시각아이디문제언어결과실행 시간메모리
992542SN0WM4NRobot (JOI21_ho_t4)C++14
0 / 100
3075 ms330640 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define sort undefined_function // To use stable_sort instead sort #define bpc __builtin_popcount #define ull unsigned long long #define ld double #define ll long long #define mp make_pair #define F first #define S second #pragma GCC optimize("O3") #ifdef LOCAL #include "debug.h" #else #define dbg(...) 0 #endif using namespace __gnu_pbds; using namespace std; typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> Tree; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll INF = 9223372036854775807LL; const ll inf = 2147483647; const ll MOD = 1e9 + 7; //[998244353, 1e9 + 7, 1e9 + 13] const ld PI = acos(-1); const ll NROOT = 500; ll binpow(ll a, ll b, ll _MOD = -1) { if (_MOD == -1) _MOD = MOD; ll res = 1; for (; b; b /= 2, a *= a, a %= _MOD) if (b & 1) res *= a, res %= _MOD; return res; } void set_IO(string s) { #ifndef LOCAL string in = s + ".in"; string out = s + ".out"; freopen(in.c_str(), "r", stdin); freopen(out.c_str(), "w", stdout); #endif } bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);} ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a * b / gcd(a, b);} ll ceil(ll a, ll b) {return (a + b - 1) / b;} ll invmod(ll a) {return binpow(a, MOD - 2);} int n, m; struct edge{ int b, c; ll p; edge(int _b, int _c, ll _p) { b = _b; c = _c; p = _p; } }; vector<vector<edge>> g; vector<map<int, ll>> dis; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; g.resize(n + 1); dis.resize(n + 1); vector<map<int, ll>> val(n + 1); vector<map<int, ll>> MAX(n + 1); for (int i = 1; i <= m; i ++) { int a, b, c; ll p; cin >> a >> b >> c >> p; g[a].push_back(edge(b, c, p)); g[b].push_back(edge(a, c, p)); val[a][c] += p; val[b][c] += p; MAX[a][c] = max(MAX[a][c], p); MAX[b][c] = max(MAX[b][c], p); } using T = pair<ll, pair<int, int>>; priority_queue<T, vector<T>, greater<T>> q; q.push({0, {1, 0}}); while (!q.empty()) { ll d = q.top().F; auto [x, c] = q.top().S; q.pop(); if (dis[x].find(c) != dis[x].end()) continue; dis[x][c] = d; for (auto &y : g[x]) { q.push({d + y.p, {y.b, 0}}); if (c == 0) { q.push({d + val[x][y.c] - y.p, {y.b, y.c}}); if (MAX[x][y.c] != val[x][y.c]) q.push({d + val[x][y.c] - MAX[x][y.c], {y.b, 0}}); } else { if (c != y.c) { q.push({d + val[x][y.c] - y.p, {y.b, y.c}}); if (MAX[x][y.c] != y.p) q.push({d + val[x][y.c] - MAX[x][y.c], {y.b, 0}}); } } } } ll ans = INF; for (auto &x : dis[n]) ans = min(ans, x.S); dbg(dis[n]); cout << (ans == INF ? -1 : ans) << '\n'; return 0; }

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

Main.cpp: In function 'int32_t main()':
Main.cpp:100:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |   auto [x, c] = q.top().S;
      |        ^
Main.cpp:18:19: warning: statement has no effect [-Wunused-value]
   18 |  #define dbg(...) 0
      |                   ^
Main.cpp:128:2: note: in expansion of macro 'dbg'
  128 |  dbg(dis[n]);
      |  ^~~
Main.cpp: In function 'void set_IO(std::string)':
Main.cpp:47:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  freopen(in.c_str(),  "r",  stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:48:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  freopen(out.c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...