oj.uz

Submission #322566

# Submission time Handle Problem Language Result Execution time Memory
322566 2020-11-14T23:11:25 Z Farrius Commuter Pass (JOI18_commuter_pass) C++11
15 / 100
 508 ms 21820 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int MX = 1e5 + 5;
const ll INF = 1e18;

vector<pair<int, int>> g[MX];
vector<ll> d(MX, INF);
vector<int> par(MX, -1);
priority_queue<pair<ll, int>> pq;
bool vis[MX];
set<pair<int, int>> free_route;

void dijkstra (int source) {
	d[source] = 0;
	pq.push(make_pair(0, source));
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto v : g[u]) {
			if (d[v.first] > d[u] + v.second) {
				d[v.first] = d[u] + v.second;
				pq.push(make_pair(-d[v.first], v.first));
				par[v.first] = u;
			}
		}
	}
}

ll dijkstra2 (int source, int obj) {
	fill(d.begin(), d.end(), INF);
	memset(vis, false, sizeof(vis));
	d[source] = 0;
	pq.push(make_pair(0, source));
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto v : g[u]) {
			ll travel = d[u] + (free_route.count(make_pair(u, v.first)) ? 0 : v.second);
			if (d[v.first] > travel) {
				d[v.first] = travel;
				pq.push(make_pair(-d[v.first], v.first));
			}
		}
	}
	return d[obj];
}

int main () {
	int n, m, s, t, us, vs;
	cin >> n >> m >> s >> t >> us >> vs;
	for (int i = 0; i < m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		g[u].push_back(make_pair(v, c));
		g[v].push_back(make_pair(u, c));
	}
	dijkstra(s);
	int k = t;
	while (par[k] != -1) {
		free_route.insert(make_pair(k, par[k]));
		free_route.insert(make_pair(par[k], k));
		k = par[k];
	}
	ll sol = dijkstra2(vs, us);
	cout << sol << '\n';
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 16224 KB Output is correct
2 Correct 358 ms 14948 KB Output is correct
3 Correct 477 ms 21088 KB Output is correct
4 Incorrect 350 ms 16224 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 18400 KB Output is correct
2 Correct 434 ms 18656 KB Output is correct
3 Correct 433 ms 17072 KB Output is correct
4 Correct 431 ms 17524 KB Output is correct
5 Correct 456 ms 19168 KB Output is correct
6 Correct 469 ms 20448 KB Output is correct
7 Correct 485 ms 21820 KB Output is correct
8 Correct 456 ms 18656 KB Output is correct
9 Correct 441 ms 19040 KB Output is correct
10 Correct 493 ms 17120 KB Output is correct
11 Correct 254 ms 15104 KB Output is correct
12 Correct 508 ms 20832 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 16224 KB Output is correct
2 Correct 358 ms 14948 KB Output is correct
3 Correct 477 ms 21088 KB Output is correct
4 Incorrect 350 ms 16224 KB Output isn't correct
5 Halted 0 ms 0 KB -