Submission #401359

#	Time	Username	Problem	Language	Result	Execution time	Memory
401359		Jorge213	Toll (APIO13_toll)	C++17	0 / 100	4 ms	4940 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pil = pair<int, long long>;
using pli = pair<long long, int>;
const int N = 1e5 + 10;
int n, m, k, p[N];
bool vis[N];
vector<pil> adjList[N];
vector<int> specialList[N];

struct Edge {
	int u;
	long long w, c;

	bool operator<(const Edge &e) const {
		if (w == e.w) 
			return p[u] * c < p[e.u] * e.c;
		return w > e.w;
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k; 

	int ai, bi;
	long long ci;
	for (int i = 0; i < m; i++) {
		cin >> ai >> bi >> ci;
		adjList[ai].push_back({bi, ci});
		adjList[bi].push_back({ai, ci});
	}

	int xi, yi;
	for (int i = 0; i < k; i++) {
		cin >> xi >> yi;
		specialList[xi].emplace_back(yi);
		specialList[yi].emplace_back(xi);
	}

	for (int i = 1; i <= n; i++) {
		cin >> p[i];
	}

	priority_queue<Edge> pq;
	pq.push({1, 0, 0});

	set<int> special;

	long long ans = 0;
	while (!pq.empty()) {
		auto [v, wv, c] = pq.top();
		pq.pop();

		if (vis[v])
			continue;

		vis[v] = true;
		ans += p[v] * c;

		for (int u : specialList[v]) {
			if (vis[u]) continue;
			special.insert(u);
		}

		for (auto [u, w] : adjList[v]) {
			if (vis[u]) continue;
			pq.push({u, w, c});

			if (special.count(u)) {
				pq.push({u, w, c + w});
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22