oj.uz

Submission #745945

# Submission time Handle Problem Language Result Execution time Memory
745945 2023-05-21T09:51:21 Z vjudge1 Cities (BOI16_cities) C++17
0 / 100
 350 ms 17768 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;

struct edge {
	int to;
	ll w;
	bool operator<(const edge& e)const {
		return w > e.w;
	}
};

const int maxn = 100001;

vector<edge> g[maxn];
void dijkstra(int a, vector<ll>& da) {
	priority_queue<edge> q;
	q.push({ a, 0 });
	da[a] = 0;
	while (!q.empty()) {
		edge e = q.top();
		q.pop();
		if (da[e.to] < e.w)continue;
		for (edge i : g[e.to]) {
			if (da[i.to] < 0 || da[i.to] > da[e.to] + i.w) {
				da[i.to] = da[e.to] + i.w;
				q.push({ i.to, da[i.to] });
			}
		}
	}
	return;
}


int main()
{
	int n, k, m;
	cin >> n >> k >> m;
	int a, b, c;
	cin >> a >> b >> c;
	for (int i = 0; i < m; i++) {
		int a, b;
		ll w;
		cin >> a >> b >> w;
		g[a].push_back({ b, w });
		g[b].push_back({ a, w });
	}
	vector<ll> da(n + 1, -1), db(n + 1, -1), dc(n + 1, -1);
	dijkstra(a, da);
	dijkstra(b, db);
	dijkstra(c, dc);

	ll ans = INT64_MAX;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, da[i] + db[i] + dc[i]);
	}
	cout << ans << endl;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 17140 KB Output is correct
2 Correct 350 ms 17768 KB Output is correct
3 Correct 140 ms 10212 KB Output is correct
4 Correct 156 ms 11652 KB Output is correct
5 Runtime error 4 ms 5076 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -