Submission #476028

#TimeUsernameProblemLanguageResultExecution timeMemory
476028CodeChamp_SSRobot (JOI21_ho_t4)C++17
100 / 100
1117 ms96072 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define ff first #define ss second #define pb push_back #define eb emplace_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define setbits(x) __builtin_popcountll(x) #define zrobits(x) __builtin_ctzll(x) #define sz(v) (int)v.size() #define ps(y) cout << fixed << setprecision(y) #define ms(arr, v) memset(arr, v, sizeof(arr)) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define trav(x, v) for(auto &x: v) #define w(t) int t; cin >> t; while(t--) #define rep(i, a, b) for(int i = a; i <= b; i++) #define rrep(i, a, b) for(int i = a; i >= b; i--) #define rep0(i, n) rep(i, 0, n - 1) #define rrep0(i, n) rrep(i, n - 1, 0) #define rep1(i, n) rep(i, 1, n) #define rrep1(i, n) rrep(i, n, 1) #define inp(arr, n) rep0(i, n) cin >> arr[i]; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pii; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<pii> vp; typedef vector<bool> vb; typedef vector<string> vs; typedef map<ll, ll> mii; typedef map<char, ll> mci; typedef priority_queue<ll> pq_mx; typedef priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq_mn; typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> pbds; /* * find_by_order(i) -> returns an iterator to the element at ith position (0 based) * order_of_key(i) -> returns the position of element i (0 based) */ const int N = 1e5 + 5; const int mod = 1e9 + 7; //const int mod = 998244353; const ll inf = 1e18; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void fio() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); } struct Edge { int v, c; ll p; }; int n, m; ll dp[N]; vector<Edge> gr[N]; map<int, vector<Edge>> cgr[N]; mii dp1[N], pre[N]; int main() { fio(); cin >> n >> m; rep0(x, m) { int u, v, c; ll p; cin >> u >> v >> c >> p; gr[u].pb({v, c, p}), gr[v].pb({u, c, p}); cgr[u][c].pb({v, c, p}), cgr[v][c].pb({u, c, p}); pre[u][c] += p, pre[v][c] += p; } rep0(x, n + 1) dp[x] = inf; pq_mn q; q.push({0, 1, 0}), dp[1] = 0; while (!q.empty()) { auto[cost, cur, col] = q.top(); q.pop(); if (col) { if (dp1[cur][col] != cost) continue; trav(neigh, cgr[cur][col]) { if (neigh.c != col) continue; // we can't flip the same edge again ll curCost = pre[cur][neigh.c] - neigh.p + cost; if (curCost < dp[neigh.v]) { dp[neigh.v] = curCost; q.push({dp[neigh.v], neigh.v, 0}); } } } else { if (dp[cur] != cost) continue; trav(neigh, gr[cur]) { // we don't flip this edge ll curCost = pre[cur][neigh.c] - neigh.p + cost; if (curCost < dp[neigh.v]) { dp[neigh.v] = curCost; q.push({dp[neigh.v], neigh.v, 0}); } // we flip this edge but not others with the same color curCost = neigh.p + cost; if (curCost < dp[neigh.v]) { dp[neigh.v] = curCost; q.push({dp[neigh.v], neigh.v, 0}); } // we don't include this edge and robot will leave 'cur' with some other edge having color 'col' curCost = cost; if (!dp1[neigh.v].count(neigh.c) or dp1[neigh.v][neigh.c] > curCost) { dp1[neigh.v][neigh.c] = curCost; q.push({curCost, neigh.v, neigh.c}); } } } } cout << (dp[n] == inf ? -1 : dp[n]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...