Submission #1265195

#TimeUsernameProblemLanguageResultExecution timeMemory
1265195nhathanhCommuter Pass (JOI18_commuter_pass)C++20
100 / 100
233 ms19048 KiB
#include<bits/stdc++.h> using namespace std; #define el "\n" #define pii pair<int,int> #define fi first #define se second #define int long long #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);} const int N=1e5+10; const int M=2e5+10; int n,m,s,t,u,v,ans=LLONG_MAX; int du[N],dv[N],dis[N],dp[2][N]; int a,b,c; vector<pii>g[N]; class cmp { public: bool operator()(pii x,pii y) { return x.se>y.se; } }; priority_queue<pii,vector<pii>,cmp>temp; void dij(int x,int arr[]) { fill(arr,arr+n+1,1e15); arr[x]=0; temp.push({x,0LL}); while(!temp.empty()) { pii p=temp.top(); temp.pop(); for(pii z : g[p.fi]) { if(arr[z.fi]<=arr[p.fi]+z.se) continue; arr[z.fi]=arr[p.fi]+z.se; temp.push({z.fi,arr[z.fi]}); } } } void dijktra(int st,int ed) { fill(dp[1],dp[1]+n+1,1e15); fill(dp[0],dp[0]+n+1,1e15); fill(dis,dis+1+n,1e15); dis[st]=0; dp[0][st]=du[st]; dp[1][st]=dv[st]; temp.push({st,0}); while(!temp.empty()) { pii p=temp.top(); temp.pop(); for(pii z : g[p.fi]) { if(dis[z.fi]<dis[p.fi]+z.se) continue; if(dis[z.fi]>dis[p.fi]+z.se) { dis[z.fi]=dis[p.fi]+z.se; dp[0][z.fi]=min(du[z.fi],dp[0][p.fi]); dp[1][z.fi]=min(dv[z.fi],dp[1][p.fi]); temp.push({z.fi,dis[z.fi]}); } else if(min(du[z.fi],dp[0][p.fi])+min(dv[z.fi],dp[1][p.fi])<=dp[0][z.fi]+dp[1][z.fi]) { dp[0][z.fi]=min(du[z.fi],dp[0][p.fi]); dp[1][z.fi]=min(dv[z.fi],dp[1][p.fi]); } } } ans=min(ans,dp[0][ed]+dp[1][ed]); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); file("a"); cin>>n>>m>>s>>t>>u>>v; for(int i=1;i<=m;i++) { cin>>a>>b>>c; g[a].push_back({b,c}); g[b].push_back({a,c}); } dij(u,du); dij(v,dv); dijktra(s,t); dijktra(t,s); ans=min(ans,du[v]); cout<<ans; return 0; }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:8:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:82:5: note: in expansion of macro 'file'
   82 |     file("a");
      |     ^~~~
commuter_pass.cpp:8:83: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                                                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:82:5: note: in expansion of macro 'file'
   82 |     file("a");
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...