| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 860228 | 2023-10-12T09:17:24 Z | phongcd | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const int M = 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;
int n, m, k;
vector <ill> g[N];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < m; i ++) {
ll u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector <ill> d(n);
for (int i = 0; i < n; i ++) d[i] = {INF, INF};
set <ill> h;
for (int i = 0, u; i < k; i ++) {
cin >> u;
h.insert({0, u});
d[u] = {0, 0};
}
vector <bool> p(n);
while (!h.empty()) {
int u = (*h.begin()).se;
ll dis = (*h.begin()).fi;
h.erase(h.begin());
if (p[u]) continue;
p[u] = 1;
for (ill e: g[u]) {
int v = e.fi; ll w = e.se;
if (d[v].fi > dis + w) {
d[v] = {dis + w, d[v].fi};
h.insert({d[v].se, v});
}
else if (d[v].se > dis + w) {
d[v].se = dis + w;
h.insert({d[v].se, v});
}
}
}
cout << d[0].se;
}
/*
/\_/\ zzZ
(= -_-)
/ >u >u
*/