Submission #314697

#TimeUsernameProblemLanguageResultExecution timeMemory
314697aZvezdaOlympic Bus (JOI20_ho_t4)C++14
0 / 100
1082 ms5632 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #define endl "\n" typedef long long ll; template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;} template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;} template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const ll mod = 1e12 + 7; #define out(x) "{" << (#x) << ": " << x << "} " const ll MAX_N = 2e2 + 10, MAX_W = 1e5 + 10; vector<pair<pair<ll, ll>, pair<ll, ll> > > edges; bool off[MAX_W]; vector<pair<pair<ll, ll>, ll> > g[MAX_N]; ll dist[4][MAX_N]; ll n, m; void dij(ll ind, ll start) { for(ll i = 0; i < MAX_N; i ++) { dist[ind][i] = mod; } priority_queue<pair<ll, ll> > pq; pq.push({0, start}); dist[ind][start] = 0; while(!pq.empty()) { auto curr = pq.top(); pq.pop(); curr.first *= -1; for(auto it : g[curr.second]) { if(off[it.second]) {continue;} ll nxt = it.first.first; if(dist[ind][nxt] > curr.first + it.first.second) { dist[ind][nxt] = curr.first + it.first.second; pq.push({-dist[ind][nxt], nxt}); } } } return; cout << "Started from " << start << endl; for(ll i = 1; i <= n; i ++) { cout << dist[ind][i] << " "; } cout << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; edges.resize(m); for(ll i = 0; i < m; i ++) { cin >> edges[i]; off[2 * i] = false; off[2 * i + 1] = true; g[edges[i].first.first].push_back({{edges[i].first.second, edges[i].second.first}, 2 * i}); g[edges[i].first.second].push_back({{edges[i].first.first, edges[i].second.first}, 2 * i + 1}); } dij(0, 1); dij(1, n); ll ret = dist[0][n] + dist[1][1]; for(ll i = 0; i < m; i ++) { int u = edges[i].first.first, v = edges[i].first.second, cost = edges[i].second.first; if(dist[0][v] + cost > dist[1][u] && dist[0][v] + cost > dist[1][u]) {continue;} off[2 * i] = true; off[2 * i + 1] = false; dij(2, 1); dij(3, n); chkmin(ret, edges[i].second.second + dist[2][n] + dist[3][1]); off[2 * i] = false; off[2 * i + 1] = true; } if(ret < mod) { cout << ret << endl; } else { cout << -1 << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...