Submission #865919

#TimeUsernameProblemLanguageResultExecution timeMemory
865919RequiemCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
280 ms54036 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #define MOD 1000000007 #define INF 1e18 #define fi first #define se second #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORD(i,a,b) for(int i=a;i>=b;i--) #define sz(a) ((int)(a).size()) #define endl '\n' #define pi 3.14159265359 #define TASKNAME "bus" template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } using namespace std; typedef pair<int,int> ii; typedef pair<int,ii> iii; typedef vector<int> vi; const int MAXN = 2e5 + 9; int n,m,s,t,u,v,distfroms[MAXN],distfromu[MAXN],distfromv[MAXN],degree[MAXN]; vector<ii> g[MAXN]; set<int> traceback[MAXN]; vector<int> shortestpath[MAXN]; void dijkstra(int start,int dist[],bool kt){ for(int i=1;i<=n;i++){ dist[i] = INF; } priority_queue<ii,vector<ii>,greater<ii>> pq; dist[start] = 0; pq.push({0,start}); while(!pq.empty()){ int u = pq.top().se; int du = pq.top().fi; pq.pop(); if (du > dist[u]) continue; for(auto pt: g[u]){ int v = pt.fi; int w = pt.se; if (dist[v] > dist[u] + w){ dist[v] = dist[u] + w; pq.push({dist[v],v}); if (kt) traceback[v].clear(); if (kt) traceback[v].insert(u); } else if (dist[v] == dist[u] + w){ if (kt) traceback[v].insert(u); } } } } int best1[MAXN],best2[MAXN]; bool visited[MAXN]; main() { fast; // freopen(TASKNAME".inp","r",stdin); // freopen(TASKNAME".out","w",stdout); cin>>n>>m; cin>>s>>t; cin>>u>>v; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; g[u].pb({v,w}); g[v].pb({u,w}); } dijkstra(s,distfroms,1); dijkstra(u,distfromu,0); dijkstra(v,distfromv,0); queue<int> q; q.push(t); visited[t] = true; // for(int i=1;i<=n;i++){ // for(auto x: traceback[i]){ // cout<<x<<' '; // } // cout<<endl; // } // cout<<endl; while (!q.empty()){ int u = q.front(); q.pop(); // cout<<u<<endl; for(auto v: traceback[u]){ shortestpath[v].pb(u); // cout<<v<<' '<<u<<endl; degree[u]++; if (!visited[v]){ visited[v] = true; q.push(v); } } } q.push(s); int ans = distfromu[v]; memset(best1,0x3f,sizeof(best1)); memset(best2,0x3f,sizeof(best2)); memset(visited,false,sizeof(visited)); while(!q.empty()){ int u = q.front(); q.pop(); best1[u] = min(best1[u], distfromu[u]); best2[u] = min(best2[u], distfromv[u]); // cout<<u<<' '<<best1[u]<<' '<<best2[u]<<endl; ans = min(ans, best1[u] + distfromv[u]); ans = min(ans, best2[u] + distfromu[u]); for(auto v: shortestpath[u]){ degree[v]--; best1[v] = min(best1[v],best1[u]); best2[v] = min(best2[v],best2[u]); if (degree[v] == 0){ q.push(v); } } } cout<<ans<<endl; }

Compilation message (stderr)

commuter_pass.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...