Submission #1197960

#TimeUsernameProblemLanguageResultExecution timeMemory
1197960guanexRobot (JOI21_ho_t4)C++20
34 / 100
3096 ms64600 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' //data structures typedef pair<ll, ll> ii; typedef vector<ii> vii; typedef vector<ll> vll; typedef vector<ll> vi; typedef vector<vector<ll>> vvi; #define pb push_back #define sz(a) ((int)a.size()) #define whole(v) v.begin(), v.end() #define rwhole(v) v.rbegin(), v.rend() #define pqueue priority_queue //answers const ll inf = ll(1e18); // read arr vec matr etc #define fill(x, y) memset(x, y, sizeof(x)) // Solution struct cmp{ bool operator()(vi &a, vi &b){ return a[0] > b[0]; } }; void tc(){ int n, m; cin >> n >> m; ll dp[m][2]; //edge idx, color matters y/n vector<vector<int>> ed(n); vector<vector<int>> edges; vector<unordered_map<int, ll>> x(n); for(int i = 0; i < m; ++i){ dp[i][0] = inf; dp[i][1] = inf; int u, v, col, cost; cin >> u >> v >> col >> cost; u--; v--; edges.pb({u, v, col, cost}); ed[u].pb(i); ed[v].pb(i); x[u][col] += cost; x[v][col] += cost; } pqueue<vi, vvi, cmp> pq; ll totcost = 0; bool othernode = 0; for(auto e:ed[0]){ totcost = x[0][edges[e][2]]; totcost -= edges[e][3]; othernode = 1; if(edges[e][0] != 0){ othernode = 0; } pq.push({edges[e][3], e, othernode, 0}); pq.push({totcost, e, othernode, 1}); dp[e][0] = edges[e][3]; dp[e][1] = totcost; } ll cost = 0; while(!pq.empty()){ int idx = pq.top()[1]; cost = pq.top()[0]; int no = edges[idx][pq.top()[2]]; bool fat = pq.top()[3]; pq.pop(); if(dp[idx][fat] != cost)continue; for(auto e:ed[no]){ if(e == idx)continue; bool me = 0; if(edges[e][0] == no){ me = 1; } totcost = x[no][edges[e][2]]; totcost -= edges[e][3]; if(fat == 0 && edges[idx][2] == edges[e][2]){ totcost -= edges[idx][3]; } if(dp[e][0] > cost + edges[e][3]){ dp[e][0] = cost + edges[e][3]; pq.push({cost + edges[e][3], e, me, 0}); } if(dp[e][1] > cost + totcost){ dp[e][1] = cost + totcost; pq.push({cost + totcost, e, me, 1}); } } } ll ans = inf; for(auto e:ed[n-1]){ ans = min(ans, min(dp[e][0], dp[e][1])); } if(ans == inf) cout << -1 << endl; else cout << ans << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while(t--){ tc(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...