Submission #749120

#TimeUsernameProblemLanguageResultExecution timeMemory
749120onebit1024Commuter Pass (JOI18_commuter_pass)C++17
15 / 100
2067 ms31680 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define all(c) c.begin(), c.end() #define endl "\n" const double PI=3.141592653589; void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x) #else #define dbg(x...) #endif int n,m; vector<vector<int>>nadj; vector<vector<pair<int,int>>>adj; int res; vector<int> dij(int s){ vector<int>dist(n+1,1e18); dist[s] = 0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; pq.push({0,s}); while(!pq.empty()){ int d = pq.top().first, u = pq.top().second; pq.pop(); if(dist[u]!=d)continue; for(auto &[v,c] : adj[u]){ int cur_dist = dist[v], new_dist = dist[u]+c; if(new_dist < cur_dist){ dist[v] = new_dist; pq.push({new_dist, v}); } } } return dist; } set<int>mnu,mnv; vector<int>dists,distt,distu,distv; void dfs(int q){ mnu.insert(distu[q]); mnv.insert(distv[q]); res = min(res, *mnu.begin()+*mnv.begin()); for(int v : nadj[q]){ dfs(v); } mnu.erase(distu[q]); mnv.erase(distv[q]); } void solve() { cin >> n >> m; adj.resize(n+1); nadj.resize(n+1); int s,t,u,v; cin >> s >> t >> u >> v; for(int i = 1;i<=m;++i){ int u,v,c; cin >> u >> v >> c; adj[u].pb({v,c}); adj[v].pb({u,c}); } dists = dij(s); distt = dij(t); distu = dij(u); distv = dij(v); for(int i =1;i<=n;++i){ for(auto &[v,c] : adj[i]){ // check if edge i->v (directed) lies on shortest path from s->t if(dists[i]+c+distt[v] == dists[t]){ nadj[i].pb(v); } } } res = distu[v]; dfs(s); cout << res << endl; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int T=1; for(int i = 1;i<=T;++i) { // cout << "Case #" << i << ": "; solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...