답안 #377005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377005	2021-03-12T17:05:27 Z	astoria	Soccer (JOI17_soccer)	C++14	35 / 100	571 ms	35040 KB

soccer

#include "bits/stdc++.h"
using namespace std;

#define int long long

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int h,w,a,b,c,n;
	cin>>h>>w>>a>>b>>c>>n;
	
	int s[n],t[n];
	for(int i=0; i<n; i++) cin>>s[i]>>t[i];
	
	vector<pair<int,int> > adj[n];
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			int difs = abs(s[i]-s[j]);
			int dift = abs(t[i]-t[j]);
			
			int optOne = (a*difs) + b + (c*dift);
			if(difs==0) optOne-=b;
			int optTwo = (a*dift) + b + (c*difs);
			if(dift==0) optTwo-=b;
			int optThree = (c*difs) + (c*dift);
			
			int dist = min(min(optOne,optTwo),optThree);
			adj[i].push_back({j,dist});
			adj[j].push_back({i,dist});
		}
	}
	
	int dist[n];
	memset(dist,-1,sizeof(dist));
	dist[0] = 0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	pq.push({0,0});
	while(!pq.empty()){
		int v = pq.top().first, di = pq.top().second; pq.pop();
		if(dist[v] != di) continue;
		for(auto ii : adj[v]){
			int nv = ii.first, nd = ii.second+di;
			if(dist[nv] != -1 && dist[nv] <= nd) continue;
			dist[nv] = nd;
			pq.push({nv,nd});
		}
	}
	cout<<dist[n-1];
	
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct

Subtask #2

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	876 KB	Output is correct
3	Correct	2 ms	768 KB	Output is correct
4	Correct	2 ms	876 KB	Output is correct
5	Correct	4 ms	2028 KB	Output is correct
6	Correct	571 ms	35040 KB	Output is correct
7	Correct	83 ms	33276 KB	Output is correct
8	Correct	96 ms	33260 KB	Output is correct
9	Correct	57 ms	33132 KB	Output is correct
10	Correct	54 ms	33260 KB	Output is correct
11	Correct	65 ms	33136 KB	Output is correct
12	Correct	2 ms	1644 KB	Output is correct
13	Correct	434 ms	35040 KB	Output is correct
14	Correct	63 ms	33132 KB	Output is correct
15	Correct	63 ms	33152 KB	Output is correct

Subtask #3

0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	876 KB	Output is correct
8	Correct	2 ms	768 KB	Output is correct
9	Correct	2 ms	876 KB	Output is correct
10	Correct	4 ms	2028 KB	Output is correct
11	Correct	571 ms	35040 KB	Output is correct
12	Correct	83 ms	33276 KB	Output is correct
13	Correct	96 ms	33260 KB	Output is correct
14	Correct	57 ms	33132 KB	Output is correct
15	Correct	54 ms	33260 KB	Output is correct
16	Correct	65 ms	33136 KB	Output is correct
17	Correct	2 ms	1644 KB	Output is correct
18	Correct	434 ms	35040 KB	Output is correct
19	Correct	63 ms	33132 KB	Output is correct
20	Correct	63 ms	33152 KB	Output is correct
21	Correct	1 ms	640 KB	Output is correct
22	Incorrect	2 ms	748 KB	Output isn't correct
23	Halted	0 ms	0 KB	-