제출 #1115664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115664		staszic_ojuz	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1099 ms	3272 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;
		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 wyniki_dijkstra[dokad];
}

ll zrob(int v, int u, ll cost, ll d) {
	ll wnk = d;
	sasiedzi[u].push_back({v, {cost, d}});
	wnk += dijkstra(1, n, v, u);
	wnk += dijkstra(n, 1, v, u);
	sasiedzi[u].pop_back();
	return wnk;
}
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 wynik = (dijkstra(1, n, -1, -1)  + dijkstra(n,1, -1, -1));
	wynik = min(wynik, (ll)1000000000000);
	for (int i = 1; n >= i; i++) {
		for (pair<int, pair<ll, ll>> ele: sasiedzi[i]) {
			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