Submission #1115185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115185		staszic_ojuz	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1076 ms	2456 KiB

ho_t4

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

using namespace std;

const int MAXN = 203;
const int MAXM = 50003;

int n, m;

pair<pair<int, int>, pair<int, int>> krawedzie[MAXM];
vector<int> sasiedzi[MAXN]; //indeksy krawedzi

bool odwiedzone[MAXN];
int wynik_dijkstra[MAXN];

int dijkstra(int skad, int dokad, int ind) {
	for (int i = 0; MAXN > i; i++) {
		odwiedzone[i] = false;
		wynik_dijkstra[i] = -1;
	}
	
	priority_queue<pair<int, int>> kopiec;
	kopiec.push({0, skad});
	
	pair<int, int> p1;
	int aktl_v, aktl_koszt;
	
	while (!kopiec.empty()) {
		p1 = kopiec.top();
		kopiec.pop();
		aktl_koszt = -p1.first;
		aktl_v = p1.second;
		if (odwiedzone[aktl_v]) continue;
		odwiedzone[aktl_v] = true;
		wynik_dijkstra[aktl_v] = aktl_koszt;
		if (aktl_v == krawedzie[ind].first.second) {
			if (!odwiedzone[krawedzie[ind].first.first]) {
				kopiec.push({-(aktl_koszt + krawedzie[ind].second.first), krawedzie[ind].first.first});
			}
		}
		for (int sasd: sasiedzi[aktl_v]) {
			if (odwiedzone[krawedzie[ind].first.second]) continue;
			if (sasd == ind) continue;
			kopiec.push({-(aktl_koszt + krawedzie[sasd].second.first), krawedzie[sasd].first.second});
		}
	}
	return wynik_dijkstra[dokad];
}

int zrob(int ind) {
	int p1;
	int wynik = krawedzie[ind].second.second;
	p1 = dijkstra(1, n, ind);
	if (p1 == -1) return 2000000000;
	wynik += p1;
	p1 = dijkstra(n, 1, ind);
	if (p1 == -1) return 2000000000;
	wynik += p1;
	return wynik;
}

int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	
	cin >> n >> m;
	
	int w1, w2, w3, w4;
	
	for (int i = 0; m > i; i++) {
		cin >> w1 >> w2 >> w3 >> w4;
		krawedzie[i] = {{w1, w2}, {w3, w4}};
		sasiedzi[w1].push_back(i);
	}
	int p1;
	int wynik;
	p1 = dijkstra(1, n, MAXM - 1);
	if (p1 == -1) {
		wynik = 2000000000;
	} else {
		wynik = p1;
		p1= dijkstra(n, 1, MAXM - 1);
		if (p1 == -1) {
			wynik = 2000000000;
		} else {
			wynik += p1;
		}
	}
	
	for (int i = 0; m > i; i++) {
		wynik = min(wynik, zrob(i));
	}
	if (wynik == 2000000000) wynik = -1;
	cout << wynik;
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63