Submission #830652

#TimeUsernameProblemLanguageResultExecution timeMemory
830652RaresFelixRobot (JOI21_ho_t4)C++17
24 / 100
779 ms81836 KiB
#include <bits/stdc++.h> #pragma GCC optimize("trapv") using namespace std; using ll = long long; const ll INF = 1e18; const int MN = 100001; int n, m; struct Edge { int cul, cost, dest; }; vector<Edge> L[MN]; vector<pair<int, ll> > G[MN]; /// nod, cost ll Cost[MN]; map<int, int> Fr[MN]; map<int, ll> Suma[MN]; map<int, pair<int, int> > Other[MN]; int main() { cin >> n >> m; for(int i = 1; i <= m; ++i) { int u, v, c, w; cin >> u >> v >> c >> w; L[u].push_back({c, w, v}); L[v].push_back({c, w, u}); } for(int i = 1; i <= n; ++i) { for(auto it : L[i]) { ++Fr[i][it.cul]; Suma[i][it.cul] += it.cost; } for(auto &it : L[i]) { it.cost = min((long long)it.cost, Suma[i][it.cul] - it.cost); } } for(int i = 1; i <= n; ++i) { for(auto it : L[i]) { if(Fr[i][it.cul] == 1) { G[i].push_back(make_pair(it.dest, 0)); } else { if(Fr[i][it.cul] == 2) { if(!Other[i].count(it.cul)) Other[i][it.cul] = make_pair(it.dest, it.cost); else { int a = Other[i][it.cul].first, b = it.dest, cul = it.cul; ll ca = Other[i][it.cul].second, cb = it.cost, c = min(ca, cb); if(Fr[a][cul] == 1) G[a].push_back(make_pair(b, c)); else G[a].push_back(make_pair(b, ca)); if(Fr[b][cul] == 1) G[b].push_back(make_pair(a, c)); else G[b].push_back(make_pair(a, cb)); } } G[i].push_back(make_pair(it.dest, it.cost)); } } } priority_queue<pair<ll, int> > PQ; PQ.push(make_pair(0ll, 1)); for(int i = 1; i <= n; ++i) Cost[i] = INF; Cost[1] = 0; while(!PQ.empty()) { ll nod = PQ.top().second, cost = - PQ.top().first; PQ.pop(); if(Cost[nod] != cost) continue; for(auto [it, w] : G[nod]) { if(Cost[it] > Cost[nod] + w) { Cost[it] = Cost[nod] + w; PQ.push(make_pair(-Cost[it], it)); } } } if(Cost[n] == INF) { cout << "-1\n"; } else { cout << Cost[n] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...