제출 #1039813

#제출 시각아이디문제언어결과실행 시간메모리
1039813doducanhCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
230 ms29592 KiB
///breaker #include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define ii pair<int,int> #define iii pair<int,ii> #define mp make_pair const int inf=1e18+7; const int maxn=1e5+7; int du[maxn]; int dv[maxn]; vector<ii>adj[maxn]; int n,m,s,t,u,v; int dp[maxn][2]; int vst[maxn]; int d[maxn]; void dijkstra1(int start,int arr[]) { for(int i=1;i<=n;i++){ arr[i]=inf; vst[u]=0; } arr[start]=0; priority_queue<ii,vector<ii>,greater<ii>>q; q.push(mp(0,start)); while(q.size()){ int u=q.top().se; int du=q.top().fi; q.pop(); if(vst[u])continue; vst[u]=1; for(auto [v,w]:adj[u]){ if(arr[v]>du+w){ arr[v]=du+w; q.push({arr[v],v}); } } } } int dijkstra2(int start,int endd) { for(int i=0;i<=n;i++){ d[i]=inf; dp[i][0]=inf; dp[i][1]=inf; vst[i]=0; } priority_queue<iii,vector<iii>,greater<iii>>q; q.push(mp(0,mp(start,0))); while(q.size()){ int u=q.top().se.fi; int duu=q.top().fi; int par=q.top().se.se; q.pop(); if(vst[u]==0){ vst[u]=1; dp[u][0]=min(dp[par][0],du[u]); dp[u][1]=min(dp[par][1],dv[u]); d[u]=duu; for(auto [v,w]:adj[u]){ q.push(mp(duu+w,mp(v,u))); } } else if(duu==d[u]){ if(min(du[u],dp[par][0])+min(dv[u],dp[par][1])<=dp[u][0]+dp[u][1]){ dp[u][0]=min(dp[u][0],min(du[u],dp[par][0])); dp[u][1]=min(dp[u][1],min(dv[u],dp[par][1])); } } } return dp[endd][0]+dp[endd][1]; } void sol(){ cin>>n>>m; cin>>s>>t; cin>>u>>v; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } dijkstra1(u,du); int ans=du[v]; dijkstra1(v,dv); ans=min(ans,dijkstra2(s,t)); ans=min(ans,dijkstra2(t,s)); cout<<ans; } main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; while(t--){ sol(); } // you should actually read the stuff at the bottom return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         for(auto [v,w]:adj[u]){
      |                  ^
commuter_pass.cpp: In function 'long long int dijkstra2(long long int, long long int)':
commuter_pass.cpp:62:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |             for(auto [v,w]:adj[u]){
      |                      ^
commuter_pass.cpp: At global scope:
commuter_pass.cpp:94:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   94 | 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...