oj.uz

Submission #1115185

# Submission time Handle Problem Language Result Execution time Memory
1115185 2024-11-20T08:12:21 Z staszic_ojuz Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 2456 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 55 ms 336 KB Output is correct
4 Correct 58 ms 336 KB Output is correct
5 Correct 75 ms 504 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 52 ms 492 KB Output is correct
10 Correct 70 ms 336 KB Output is correct
11 Correct 57 ms 336 KB Output is correct
12 Incorrect 59 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Execution timed out 1076 ms 1796 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 55 ms 336 KB Output is correct
4 Correct 58 ms 336 KB Output is correct
5 Correct 75 ms 504 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 52 ms 492 KB Output is correct
10 Correct 70 ms 336 KB Output is correct
11 Correct 57 ms 336 KB Output is correct
12 Incorrect 59 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -