oj.uz

Submission #1115678

# Submission time Handle Problem Language Result Execution time Memory
1115678 2024-11-20T18:51:32 Z staszic_ojuz Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 3400 KB 
#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 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.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 336 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 31 ms 476 KB Output is correct
4 Correct 46 ms 508 KB Output is correct
5 Correct 36 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 2 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 3400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 336 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Execution timed out 1093 ms 2864 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 336 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 31 ms 476 KB Output is correct
4 Correct 46 ms 508 KB Output is correct
5 Correct 36 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 2 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -