21
2025-05-25 22:03:20
发布于:山西
7阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <unordered_set>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int P, C, K;
cin >> P >> C >> K;
vector<vector<pair<int, int>>> graph(P);
for (int i = 0; i < C; ++i) {
int a, b, L;
cin >> a >> b >> L;
a--; b--; // Convert to 0-based index.
graph[a].emplace_back(b, L);
graph[b].emplace_back(a, L);
}
unordered_set<int> largeFarms;
if (K > 0) {
for (int i = 0; i < K; ++i) {
int farm;
cin >> farm;
farm--;
largeFarms.insert(farm);
}
}
vector<ll> minDist(P, LLONG_MAX);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
// Initialize the priority queue with all large farms as sources.
for (int farm : largeFarms) {
minDist[farm] = 0;
pq.emplace(0, farm);
}
// Multi-source Dijkstra's algorithm.
while (!pq.empty()) {
auto [currentDist, u] = pq.top();
pq.pop();
if (currentDist > minDist[u]) continue;
for (auto [v, weight] : graph[u]) {
if (minDist[v] > currentDist + weight) {
minDist[v] = currentDist + weight;
pq.emplace(minDist[v], v);
}
}
}
// Find the minimum distance among non-large farms.
ll result = LLONG_MAX;
for (int i = 0; i < P; ++i) {
if (largeFarms.find(i) == largeFarms.end() && minDist[i] < result) {
result = minDist[i];
}
}
if (result == LLONG_MAX) {
cout << -1 << endl;
} else {
cout << result << endl;
}
return 0;
}
这里空空如也
有帮助,赞一个