제출 #1025821

#제출 시각아이디문제언어결과실행 시간메모리
1025821underwaterkillerwhaleRobot (JOI21_ho_t4)C++17
100 / 100
902 ms95168 KiB
#include <bits/stdc++.h> #define se second #define fs first #define mp make_pair #define pb push_back #define ll long long #define ii pair<ll,ll> #define ld long double #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) using namespace std; mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const int N = 1e5 + 7; const ll Mod = 1e9 + 7; const int szBL = 916; const ll INF = 1e18; const int BASE = 1337; int n, m; map<int,ll> dp[N], cost[N]; map<int, vector<pair<int, ll>>> ke[N]; void solution () { cin >> n >> m; rep (i, 1, m) { ll u, v, c, p; cin >> u >> v >> c >> p; ke[u][c].push_back({v, p}); ke[v][c].push_back({u, p}); cost[u][c] += p; cost[v][c] += p; dp[u][c] = INF; dp[v][c] = INF; } rep (i, 1, n) dp[i][0] = INF; struct Node { ll u, c, val; }; struct cmp { bool operator () (Node A, Node B) { return A.val > B.val; } }; priority_queue<Node, vector<Node>, cmp> pq; pq.push({1, 0, 0}); dp[1][0] = 0; while (!pq.empty()) { int u = pq.top().u, c = pq.top().c; ll val = pq.top().val; pq.pop(); if (u == n && c == 0) break; if (c) { if (val != dp[u][c]) continue; iter (&id, ke[u][c]) { ll v, w; tie(v, w) = id; if (dp[v][0] > dp[u][c] + cost[u][c] - w){ dp[v][0] = dp[u][c] + cost[u][c] - w; pq.push({v, 0, dp[v][0]}); } } } else { if (val != dp[u][0]) continue; iter (&id2, ke[u]) { int vc = id2.fs; iter (&id, id2.se) { ll v, w; tie(v, w) = id; if (dp[v][vc] > dp[u][0]) { dp[v][vc] = dp[u][0]; pq.push({v, vc, dp[v][vc]}); } if (dp[v][0] > dp[u][0] + w) { dp[v][0] = dp[u][0] + w; pq.push({v, 0, dp[v][0]}); } if (dp[v][0] > dp[u][0] + cost[u][vc] - w) { dp[v][0] = dp[u][0] + cost[u][vc] - w; pq.push({v, 0, dp[v][0]}); } } } } } if (dp[n][0] == INF) cout << -1 <<"\n"; else cout << dp[n][0] <<"\n"; } #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); int main () { // file("c"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll num_Test = 1; // cin >> num_Test; while(num_Test--) solution(); } /* 18 3 2 5 6 21 13 19 9 17 14 17 19 20 2 16 2 10 9 14 19 20 14 16 1 3 17 19 14 21 18 19 4 7 5 12 1 13 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...