- 选择最佳线路
1
- @ 2026-7-21 10:42:57
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
void solve() {
int n, m, s;
cin >> n >> m >> s;
// vector<vector<int>> e(n + 1, vector<int>());
vector e(n + 1, vector<pii>());
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
e[u].push_back({v, w});
}
const int inf = 1e9 + 10;
vector<int> visi(n + 1), d(n + 1, inf);
// vector<int> d(n + 1, inf);
priority_queue<pii, vector<pii>, greater<pii>> q;
int w; cin >> w; while (w--) {
int x; cin >> x;
d[x] = 0, q.push({0, x});
}
while (q.size()) {
auto [dis, u] = q.top(); q.pop();
if (visi[u]) continue;
visi[u] = 1;
for (auto [v, w] : e[u]) {
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
cout << (d[s] == inf ? -1 : d[s]) << '\n';
}
signed main() {
int t = 1;
// cin >> t;
while (t--) solve();
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/
0 条评论
目前还没有评论...
信息
- ID
- 492
- 时间
- ms
- 内存
- MiB
- 难度
- 2
- 标签
- 递交数
- 70
- 已通过
- 45
- 上传者