제출 #1096097

#제출 시각아이디문제언어결과실행 시간메모리
1096097I_FloPPed21Commuter Pass (JOI18_commuter_pass)C++14
24 / 100
2068 ms18548 KiB
#include <bits/stdc++.h> using namespace std; const int N=1e5+1; const long long infinit=1e18; int n,m,casa,scoala,mag1,mag2; long long costuri[N]; vector<int>pereche[N]; long long dp[N][2][3];//directie drum pentru 1/astfel 1 egal crescator 2 descrescator 0 bag pula; struct drum { int unde,cost; }; struct coada { int nod; long long cost; int a_folosit;//asta e de 3 tipuri int drumulet; }; struct compara { bool operator()(coada &x,coada &y) { return x.cost<y.cost; } }; void reset() { for(int i=1; i<=n; i++) { for(int j=0; j<=2; j++) for(int k=0; k<3; k++) dp[i][j][k]=infinit; } } vector<drum>adj[N]; void cauta_drum(int start) { for(int i=1; i<=n; i++) costuri[i]=infinit; priority_queue<coada,vector<coada>,compara>pq; reset(); costuri[start]=0; coada x= {start,0,0,0}; pq.push(x); while(!pq.empty()) { coada actual=pq.top(); pq.pop(); for(auto u:adj[actual.nod]) { if(costuri[u.unde]>actual.cost+u.cost) { costuri[u.unde]=actual.cost+u.cost; pq.push({u.unde,costuri[u.unde],0}); } } } } void back_drum(int start) { queue<int>cod; cod.push(start); vector<bool>viz(n+1,0); viz[start]=true; while(!cod.empty()) { int nod=cod.front(); cod.pop(); for(auto u:adj[nod]) { if(costuri[u.unde]+u.cost==costuri[nod]) { pereche[u.unde].push_back(nod); pereche[nod].push_back(u.unde); if(!viz[u.unde]) { viz[u.unde]=true; cod.push(u.unde); } } } } } void calculeaza_cost(int start) { reset(); priority_queue<coada,vector<coada>,compara>pq; dp[start][0][0]=0; pq.push({start,0,0,0}); while(!pq.empty()) { int nod,tip; long long cost; nod=pq.top().nod; cost=pq.top().cost; tip=pq.top().a_folosit; int drum=pq.top().drumulet; pq.pop(); for(auto u:adj[nod]) { long long end=cost+u.cost; if(tip>0) { if(dp[u.unde][1][0]>end) { dp[u.unde][1][0]=end; pq.push({u.unde,end,2,0}); } } else { if(dp[u.unde][0][0]>end) { dp[u.unde][0][0]=end; pq.push({u.unde,end,0,0}); } } } if(tip<2) { for(auto u:pereche[nod]) { if(drum==0) { if(costuri[nod]<costuri[u]) { if(dp[u][1][1]>dp[nod][tip][0]) { dp[u][1][1]=dp[nod][tip][0]; pq.push({u,dp[u][1][1],1,1}); } } else { if(dp[u][1][2]>dp[nod][tip][0]) { dp[u][1][2]=dp[nod][tip][0]; pq.push({u,dp[u][1][2],1,2}); } } } else { if(drum==1) { if(costuri[nod]<costuri[u]) { if(dp[u][1][1]>dp[nod][1][1]) { dp[u][1][1]=dp[nod][1][1]; pq.push({u,dp[u][1][1],1,1}); } } } else if(costuri[nod]>costuri[u]) { if(dp[u][1][2]>dp[nod][1][2]) { dp[u][1][2]=dp[nod][1][2]; pq.push({u,dp[u][1][2],1,2}); } } } } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; cin>>casa>>scoala; cin>>mag1>>mag2; for(int i=1; i<=m; i++) { int nod1,nod2,cost; cin>>nod1>>nod2>>cost; adj[nod1].push_back({nod2,cost}); adj[nod2].push_back({nod1,cost}); } cauta_drum(casa); back_drum(scoala); calculeaza_cost(mag2); long long ans=infinit; for(int i=0; i<2; i++) { for(int k=0; k<=2; k++) ans=min(ans,dp[mag1][i][k]); } cout<<ans<<'\n'; return 0; }

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

commuter_pass.cpp: In function 'void reset()':
commuter_pass.cpp:35:28: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   35 |                 dp[i][j][k]=infinit;
      |                 ~~~~~~~~~~~^~~~~~~~
commuter_pass.cpp:33:23: note: within this loop
   33 |         for(int j=0; j<=2; j++)
      |                      ~^~~
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
   35 |                 dp[i][j][k]=infinit;
      |                 ~~~~~~~^
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
commuter_pass.cpp: In function 'void cauta_drum(int)':
commuter_pass.cpp:35:28: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   35 |                 dp[i][j][k]=infinit;
      |                 ~~~~~~~~~~~^~~~~~~~
commuter_pass.cpp:33:23: note: within this loop
   33 |         for(int j=0; j<=2; j++)
      |                      ~^~~
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
   35 |                 dp[i][j][k]=infinit;
      |                 ~~~~~~~^
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
commuter_pass.cpp: In function 'void calculeaza_cost(int)':
commuter_pass.cpp:35:28: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   35 |                 dp[i][j][k]=infinit;
      |                 ~~~~~~~~~~~^~~~~~~~
commuter_pass.cpp:33:23: note: within this loop
   33 |         for(int j=0; j<=2; j++)
      |                      ~^~~
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
   35 |                 dp[i][j][k]=infinit;
      |                 ~~~~~~~^
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
commuter_pass.cpp:35:24: warning: array subscript 2 is above array bounds of 'long long int [2][3]' [-Warray-bounds]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...