oj.uz

답안 #401359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401359 2021-05-10T02:25:01 Z Jorge213 통행료 (APIO13_toll) C++17
0 / 100
 4 ms 4940 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -