Submission #1116900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116900		witek_cpp	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1066 ms	4392 KiB

ho_t4

#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 201;

int n, m;

vector<pair<int, pair<ll, ll>>> sasiedzi[MAXN]; //dokad, jaka waga krawedzi, jakie d

bool odwiedzone[MAXN];
ll wyniki_dijkstra[MAXN];

ll dijkstra(int skad, int dokad, int skad_nie_chodzic, int do_czego_nie_chodzic) {
	for (int i = 1; n >= i; i++) {
		odwiedzone[i] = false;
		wyniki_dijkstra[i] = 1000000000001;
	}
	priority_queue<pair<ll, int>> kopiec;
	kopiec.push({0, skad});
	
	pair<ll, int> p1;
	
	ll aktl_koszt;
	int aktl_v;
	
	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;
		wyniki_dijkstra[aktl_v] = aktl_koszt;
		//cout << "aktl v " << aktl_v << "\n";
		if (aktl_v == dokad) return aktl_koszt;
		for (auto sasd: sasiedzi[aktl_v]) {
			if ((aktl_v  == skad_nie_chodzic && sasd.first == do_czego_nie_chodzic) || odwiedzone[sasd.first]) continue;
			kopiec.push({-(aktl_koszt + sasd.second.first), sasd.first});
		}
	}
	return -1;
}

ll zrob(int v, int u, ll cost, ll d) {
	ll wnk = d;
	ll p1;
	sasiedzi[u].push_back({v, {cost, d}});
	p1 = dijkstra(1, n, v, u); 
	if (p1 == -1) {
		sasiedzi[u].pop_back();
		return -1;
	}
	wnk += p1;
	p1 = dijkstra(n, 1, v, u);
	if (p1 == -1) {
		sasiedzi[u].pop_back();
		return -1;
	}
	wnk += p1; 
	sasiedzi[u].pop_back();
	return wnk;
}
int lolxd;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	int w1, w2;
	ll w3, w4;
	for (int i = 0; m > i; i++) {
		cin >> w1 >> w2 >> w3 >> w4;
		sasiedzi[w1].push_back({w2, {w3, w4}});
	}
	ll p1;
	ll wynik = 0;
	p1 = dijkstra(1, n, -1, -1);
	if (p1 != -1) {
		wynik += p1;
		p1 = dijkstra(n,1, -1, -1);
		if (p1 != -1) {
			wynik += p1;
		} else {
			wynik = 1000000000000;
		}
	} else {
		wynik = 1000000000000;
	}
	for (int i = 1; n >= i; i++) {
		for (pair<int, pair<ll, ll>> ele: sasiedzi[i]) {
			p1 = zrob(i, ele.first, ele.second.first, ele.second.second);
			if (p1 != -1) {
				//cout << i << " " << ele.first << "\n";
				wynik = min(wynik, zrob(i, ele.first, ele.second.first, ele.second.second));
			}
		}
	}
	if (wynik == 1000000000000) wynik = -1;
	cout << wynik;
	return 0;
}

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