oj.uz

Submission #850587

# Submission time Handle Problem Language Result Execution time Memory
850587 2023-09-17T03:05:37 Z Qang Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 109 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, s, t, u, v;
void dijkstra(ll source, ll dest, vector<vector<ll>> &g, bool flag) {
	vector<ll> dist(n + 1, INT_MAX);
	vector<bool> visited(n + 1, false);
	vector<ll> parent(n + 1, -1);
	dist[source] = 0;
	priority_queue<pair<ll, ll>> q;
	q.push({ 0, source });
	while (!q.empty()) {
		auto curr = q.top();
		q.pop();
		if (visited[curr.second]) continue;
		visited[curr.second] = true;
		for (int i = 1; i <= n; ++i) {
			ll adj = g[curr.second][i];
			if (adj != INT_MAX && dist[curr.second] + adj < dist[i]) {
				dist[i] = dist[curr.second] + adj;
				q.push({ -dist[i], i });
				parent[i] = curr.second;
			}
		}
	}
	if (!flag) {
		ll tmp = dest;
		while (parent[tmp] != -1) {
			g[tmp][parent[tmp]] = 0;
			g[parent[tmp]][tmp] = 0;
			tmp = parent[tmp];
		}
	}
	else cout << dist[dest];
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> s >> t >> u >> v;
	vector<vector<ll>> g(n + 1, vector<ll>(n + 1, INT_MAX));
	for (int i = 0; i <= n; ++i)
		g[i][i] = 0;
	for (int i = 0; i < m; ++i) {
		ll a, b, c;
		cin >> a >> b >> c;
		g[a][b] = min(g[a][b], c);
		g[b][a] = min(g[b][a], c);
	}
	dijkstra(s, t, g, 0);
	dijkstra(u, v, g, 1);
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -