Submission #949633

#TimeUsernameProblemLanguageResultExecution timeMemory
949633ace5Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
386 ms30188 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100001; const int64_t INF = 1e18; vector<pair<int,int>> g[maxn]; vector<int> g2[maxn]; vector<int> g3[maxn]; vector<int> ts; int64_t dp[maxn]; int64_t d[maxn],ds[maxn],dt[maxn],du[maxn],dv[maxn]; int vis[maxn]; set<pair<int64_t,int>> ff; int n; void dij(int s) { for(int j = 0;j < n;++j) { d[j] = INF; vis[j] = 0; } d[s] = 0; ff.insert({0,s}); while(ff.size()) { int v = (*ff.begin()).second; ff.erase(ff.begin()); vis[v] = 1; for(auto [u,dd]:g[v]) { if(d[u] > d[v] + dd && !vis[u]) { ff.erase({d[u],u}); d[u] = d[v] + dd; ff.insert({d[u],u}); } } } return ; } void dfs(int v) { vis[v] = 1; for(auto u:g2[v]) { if(!vis[u]) { dfs(u); } } ts.push_back(v); return ; } void dfs2(int v) { vis[v] = 1; for(auto u:g3[v]) { if(!vis[u]) { dfs2(u); } } ts.push_back(v); return ; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int m; cin >> n >> m; int s,t,u,v; cin >> s >> t >> u >> v; s--; t--; u--; v--; for(int i = 0;i < m;++i) { int a,b,c; cin >> a >> b >> c; a--; b--; g[a].push_back({b,c}); g[b].push_back({a,c}); } dij(s); for(int j = 0;j < n;++j) { ds[j] = d[j]; } dij(t); for(int j = 0;j < n;++j) { dt[j] = d[j]; } dij(u); for(int j = 0;j < n;++j) { du[j] = d[j]; } dij(v); for(int j = 0;j < n;++j) { dv[j] = d[j]; } for(int v = 0;v < n;++v) { for(auto [u,d] : g[v]) { if(ds[u]-ds[v] == d && dt[v]-dt[u] == d && ds[u] + dt[u] == ds[t]) { g2[v].push_back(u); g3[u].push_back(v); } } } for(int i = 0;i < n;++i) vis[i] = 0; dfs(s); int64_t ans = du[v]; for(int i = 0;i < ts.size();++i) { dp[ts[i]] = dv[ts[i]]; for(auto u : g2[ts[i]]) { dp[ts[i]] = min(dp[ts[i]],dp[u]); } ans = min(ans,dp[ts[i]]+du[ts[i]]); } for(int i = 0;i < n;++i) vis[i] = 0; ts.clear(); dfs2(t); for(int i = 0;i < ts.size();++i) { dp[ts[i]] = dv[ts[i]]; for(auto u : g3[ts[i]]) { dp[ts[i]] = min(dp[ts[i]],dp[u]); } ans = min(ans,dp[ts[i]]+du[ts[i]]); } cout << ans << "\n"; }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i = 0;i < ts.size();++i)
      |                   ~~^~~~~~~~~~~
commuter_pass.cpp:140:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(int i = 0;i < ts.size();++i)
      |                   ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...