Submission #787819

#TimeUsernameProblemLanguageResultExecution timeMemory
787819guagua0407Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
287 ms25400 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } const int mxn=1e5+5; vector<pair<int,ll>> adj[mxn]; int n,m; int S,T,U,V; vector<int> vec; vector<ll> dij(int node){ priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq; vector<ll> d(n,(ll)1e18); d[node]=0; pq.push({0,node}); while(!pq.empty()){ auto v=pq.top(); pq.pop(); if(v.f!=d[v.s]) continue; for(auto u:adj[v.s]){ if(d[v.s]+u.s<d[u.f]){ d[u.f]=d[v.s]+u.s; pq.push({d[u.f],u.f}); } } } return d; } vector<vector<ll>> d; bool comp(int a,int b){ return d[S][a]<d[S][b]; } int main() {_ cin>>n>>m; 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--; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } d.resize(n); for(int i=0;i<n;i++){ if(i!=S and i!=T and i!=U and i!=V) continue; d[i]=dij(i); } ll ans=(ll)1e18; vector<int> vec; for(int i=0;i<n;i++){ if(d[S][i]+d[T][i]==d[S][T]) vec.push_back(i); } sort(all(vec),comp); vector<ll> mn(n,(ll)1e18); for(auto v:vec){ mn[v]=d[U][v]; for(auto u:adj[v]){ if(d[S][u.f]+u.s==d[S][v]) mn[v]=min(mn[v],mn[u.f]); } //cout<<v+1<<' '<<mn[v]<<'\n'; ans=min(ans,mn[v]+d[V][v]); } mn=vector<ll>(n,(ll)1e18); for(auto v:vec){ mn[v]=d[V][v]; for(auto u:adj[v]){ if(d[S][u.f]+u.s==d[S][v]) mn[v]=min(mn[v],mn[u.f]); } //cout<<v+1<<' '<<mn[v]<<'\n'; ans=min(ans,mn[v]+d[U][v]); } cout<<min(d[U][V],ans)<<'\n'; return 0; } //maybe its multiset not set

Compilation message (stderr)

commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...