Submission #650053

#TimeUsernameProblemLanguageResultExecution timeMemory
650053ToroTNToll (BOI17_toll)C++14
7 / 100
123 ms124232 KiB
#include<bits/stdc++.h> using namespace std; int num,n,m,t,u_i,v_i,w_i,x,y,dp[5][5][50005][25],mx,pow_2[25],st,ed,val[5],nxt[5],ans; void listdp() { for(int i=0;i<=20;i++) { printf("%d\n",i); for(int j=0;j<=mx;j++) { for(int k=0;k<num;k++) { for(int l=0;l<num;l++) { printf("%d %d %d %d\n",j,k,l,dp[k][l][j][i]); } } } printf("\n"); } } int main() { pow_2[0]=1; for(int i=1;i<=20;i++)pow_2[i]=pow_2[i-1]*2; for(int i=0;i<=4;i++) { for(int j=0;j<=4;j++) { for(int k=0;k<=50000;k++) { for(int l=0;l<=20;l++) { dp[i][j][k][l]=1e9; } } } } scanf("%d%d%d%d",&num,&n,&m,&t); mx=(n-1)/num; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u_i,&v_i,&w_i); dp[u_i%num][v_i%num][u_i/num][0]=w_i; } for(int i=1;i<=20;i++) { for(int j=0;j<=mx;j++) { for(int k=0;k<num;k++) { for(int l=0;l<num;l++) { for(int c=0;c<num;c++) { if(j+pow_2[i-1]<=mx) { dp[k][l][j][i]=min(dp[k][l][j][i],dp[k][c][j][i-1]+dp[c][l][j+pow_2[i-1]][i-1]); } } } } } } //listdp(); while(t--) { scanf("%d%d",&x,&y); st=x/num; ed=y/num; x%=num; y%=num; for(int i=0;i<num;i++)val[i]=1e9; val[x]=0; for(int i=20;i>=0;i--) { if(st+pow_2[i]<ed) { for(int j=0;j<num;j++) { nxt[j]=1e9; } for(int j=0;j<num;j++) { for(int k=0;k<num;k++) { nxt[j]=min(nxt[j],val[k]+dp[k][j][st][i]); } } st+=pow_2[i]; for(int j=0;j<num;j++) { val[j]=nxt[j]; } } } ans=1e9; for(int i=0;i<num;i++) { ans=min(ans,val[i]+dp[i][y][ed-1][0]); } if(ans==1e9) { printf("-1\n"); }else { printf("%d\n",ans); } } }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d%d%d%d",&num,&n,&m,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d%d%d",&u_i,&v_i,&w_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...