제출 #1209881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209881		witek_cpp	Soccer (JOI17_soccer)	C++20	100 / 100	714 ms	38944 KiB

soccer

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";

int h, w; //wysokosc (height) - h metrow, szeorkosc (weidht) w metrow
int n;

ll a, b, c; //koszt to odl * a + b, ruch to c

vector<pair<int, int>> zawodnicy; //{y zawodnika , x zawodnika}
vector<vector<ll>> min_dojscie;

queue<pair<pair<int, int>, ll>> kolejka_bfs;
vector<pair<int, int>> ruchy = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};


pair<int, int> p1, p2;
pair<pair<int, int>, ll> p3;
pair<pair<ll, int>, pair<int, int>> p4; //koszt , wymiar, y, x

vector<vector<vector<ll>>> dijkstra;

bool dobre(pair<int, int> pos) {
	if (pos.st < 0 || pos.st > h || pos.nd < 0 || pos.nd > w) return false;
	return true;	
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> h >> w >> a >> b >> c >> n;
	
	zawodnicy.resize(n + 1);
	f(i, 1, n + 1) cin >> zawodnicy[i].st >> zawodnicy[i].nd;
	
	min_dojscie.resize(h + 1, vector<ll>(w + 1, -1));
	
	f(i, 1, n) {
		min_dojscie[zawodnicy[i].st][zawodnicy[i].nd] = 0;
		kolejka_bfs.push({{zawodnicy[i].st, zawodnicy[i].nd}, 0});
	}
	
	while (kolejka_bfs.size()) {
		p3 = kolejka_bfs.front();
		p1 = p3.st;
		kolejka_bfs.pop();
		for (pair<int, int> ele: ruchy) {
			p2 = {p1.st + ele.st, p1.nd + ele.nd};
			if (!dobre(p2)) continue;
			if (min_dojscie[p2.st][p2.nd] != -1) continue;
			min_dojscie[p2.st][p2.nd] = p3.nd + c;
			kolejka_bfs.push({{p2.st, p2.nd}, min_dojscie[p2.st][p2.nd]});
		}
	}
	
	dijkstra.resize(5, vector<vector<ll>>(h + 1, vector<ll>(w + 1, -1)));
	
	priority_queue<pair<pair<ll, int>, pair<int, int>>> kolejka_dijsktra;
	kolejka_dijsktra.push({{0, 0}, zawodnicy[1]});
	
	ll wnk = 1000000000000000000;
	
	while (kolejka_dijsktra.size()) {
		p4 = kolejka_dijsktra.top();
		kolejka_dijsktra.pop();
		p4.st.st = -p4.st.st;
		if (dijkstra[p4.st.nd][p4.nd.st][p4.nd.nd] != -1) continue;
		dijkstra[p4.st.nd][p4.nd.st][p4.nd.nd] = p4.st.st;
		p1 = p4.nd;
		//cout << "jestem w " << p4.st.st << "   rodzaj " << p4.st.nd << "   wspolrzedne " << p4.nd.st << " " << p4.nd.nd << "\n";
		if (p4.st.nd == 0) {
			for (pair<int, int> ele: ruchy) {
				p2 = {p1.st + ele.st, p1.nd + ele.nd};
				if (!dobre(p2)) continue;
				if (dijkstra[p4.st.nd][p2.st][p2.nd] != -1) continue;
				kolejka_dijsktra.push({{-(p4.st.st + c), 0}, {p2.st, p2.nd}});
			}
			f(i, 1, 5) {
				if (dijkstra[i][p4.nd.st][p4.nd.nd] == -1) {
					kolejka_dijsktra.push({{-(p4.st.st + b), i}, {p4.nd.st, p4.nd.nd}});
				}
			}
		} else {
			if (dijkstra[0][p4.nd.st][p4.nd.nd] == -1) kolejka_dijsktra.push({{-(p4.st.st + min_dojscie[p4.nd.st][p4.nd.nd]), 0}, {p4.nd.st, p4.nd.nd}});
			p2 = p4.nd;
			p2.st += ruchy[p4.st.nd - 1].st;
			p2.nd += ruchy[p4.st.nd - 1].nd;
			if (dobre(p2)) {
				if (dijkstra[p4.st.nd][p2.st][p2.nd] == -1) {
					kolejka_dijsktra.push({{-(p4.st.st + a), p4.st.nd}, {p2.st, p2.nd}});
					//cout << "dodaje " << (p4.st.st + a) << " " <<  p4.st.nd << "    " <<  p2.st << " " << p2.nd << "\n";
				}
			}
		}
		if (p4.nd.st == zawodnicy[n].st && p4.nd.nd == zawodnicy[n].nd) {wnk = p4.st.st; break;}
	}
	
	cout << wnk;
	
	return 0;
}
	
	

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