Submission #340937

#	Time	Username	Problem	Language	Result	Execution time	Memory
340937		couplefire	Soccer (JOI17_soccer)	C++17	100 / 100	984 ms	187236 KiB

soccer

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL A,B,C;
int Head[8000005],Cnt,N,M,D[505][505],Mantot,Arrive[505][505];
struct Point{int Xh,Yh;}P[8000005];
struct Edge{int Next,To; LL W;}E[8000005];
void Add_Edge(int X1,int Y1,LL Z1){E[++Cnt].Next=Head[X1],E[Cnt].To=Y1,E[Cnt].W=Z1,Head[X1]=Cnt;}
int Change(int X0,int Y0,int K0){return K0*(N+1)*(M+1)+X0*(M+1)+Y0;}
const int Go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void BFS(){
   queue<pair<int,int> >Que;
   memset(D,0x3f,sizeof(D));
   for(int I=1;I<=Mantot;I++) Que.push(make_pair(P[I].Xh,P[I].Yh)),D[P[I].Xh][P[I].Yh]=0;
   while(!Que.empty()){
   	pair<int,int> Par=Que.front(); Que.pop();
   	Arrive[Par.first][Par.second]=0;
   	for(int I=0;I<4;I++){
   		int Nx=Par.first+Go[I][0],Ny=Par.second+Go[I][1];
   		if(Nx>N||Nx<0||Ny>M||Ny<0) continue;
   		if(D[Nx][Ny]>D[Par.first][Par.second]+1){
   			D[Nx][Ny]=D[Par.first][Par.second]+1;
   			if(!Arrive[Nx][Ny]) Que.push(make_pair(Nx,Ny)),Arrive[Nx][Ny]=1;
   		}
   	}
   }
}
struct Node{
   int Id;
   LL Dis;
   bool operator < (const Node& B)const{
   	return Dis>B.Dis;
   }
};
int Vis[8000005];
LL Best[8000005];
void Dijkstra(){
   priority_queue<Node>Q;
   memset(Best,0x3f,sizeof(Best));
   memset(Vis,0,sizeof(Vis));
   Q.push((Node){Change(P[1].Xh,P[1].Yh,4),0}),Best[Change(P[1].Xh,P[1].Yh,4)]=0;
   while(!Q.empty()){
   	Node Tp=Q.top(); Q.pop();
   	if(Vis[Tp.Id]) continue;
   	Vis[Tp.Id]=1;
   	for(int I=Head[Tp.Id];I;I=E[I].Next){
   		int Y=E[I].To;
   		if(Best[Y]<=Best[Tp.Id]+E[I].W) continue;
   		Best[Y]=Best[Tp.Id]+E[I].W,Q.push((Node){Y,Best[Y]});
   	} 
   }
}
signed main(){
   scanf("%d%d%lld%lld%lld%d",&N,&M,&A,&B,&C,&Mantot);
   for(int I=1;I<=Mantot;I++) scanf("%d%d",&P[I].Xh,&P[I].Yh);
   BFS();
   for(int I=0;I<=N;I++)
   	for(int J=0;J<=M;J++)
   		for(int U=0;U<4;U++){
   			Add_Edge(Change(I,J,U),Change(I,J,4),0LL);
   			Add_Edge(Change(I,J,4),Change(I,J,5),1LL*C*D[I][J]);
   			Add_Edge(Change(I,J,5),Change(I,J,U),1LL*B);
   			int Nx=I+Go[U][0],Ny=J+Go[U][1];
   			if(Nx<0||Ny<0||Nx>N||Ny>M) continue;
   			Add_Edge(Change(I,J,U),Change(Nx,Ny,U),1LL*A);
   			Add_Edge(Change(I,J,5),Change(Nx,Ny,5),1LL*C);
   		}
   Dijkstra();
   LL Ans=0x3f3f3f3f3f3f3f3f;
   for(int I=0;I<6;I++) Ans=min(Ans,Best[Change(P[Mantot].Xh,P[Mantot].Yh,I)]);
   printf("%lld",Ans);
   return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |    scanf("%d%d%lld%lld%lld%d",&N,&M,&A,&B,&C,&Mantot);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:55:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |    for(int I=1;I<=Mantot;I++) scanf("%d%d",&P[I].Xh,&P[I].Yh);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65