Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define int long long
- using namespace std;
- void Read(int &val) {
- val = 0; char c;
- do { c = getchar(); } while (!isdigit(c));
- while (isdigit(c)) { val = val * 10 + c - '0'; c = getchar(); }
- }
- typedef pair<int, int> ii;
- struct dataHeap {
- int u, type, val;
- dataHeap() {}; dataHeap(int u, int type, int val) : u(u), type(type), val(val) {};
- bool operator > (const dataHeap &a) const { return val > a.val; }
- };
- struct dataEdge {
- int u, v, w;
- dataEdge() {}; dataEdge(int u, int v, int w) : u(u), v(v), w(w) {};
- bool operator < (const dataEdge &a) const { return w < a.w; }
- };
- const int N = 1e5 + 4, oo = 1e17;
- int n, m, numDoor;
- vector<int> lisDoor;
- vector<ii> adj[N];
- namespace Min_Distance_To_Tree {
- int dist[N];
- priority_queue<ii, vector<ii>, greater<ii> > heap;
- int Dijkstra() {
- for (int i = 1; i <= n; ++i) dist[i] = oo; dist[1] = 0;
- heap.push(ii(0, 1));
- while (heap.size()) {
- int u = heap.top().second, du = heap.top().first; heap.pop();
- if (du != dist[u]) continue;
- for (int i = 0; i < (int) adj[u].size(); ++i) {
- int v = adj[u][i].second, uv = adj[u][i].first;
- if (dist[v] > du + uv) { dist[v] = du + uv; heap.push(ii(du+uv, v)); }
- }
- }
- int res = -1;
- for (int ver : lisDoor) res = (res == -1) ? dist[ver] : min(res, dist[ver]);
- return res;
- }
- }
- int par[N];
- int getRoot(int u) { return (par[u] < 0) ? u : (par[u] = getRoot(par[u])); }
- bool Merge(int u, int v) {
- u = getRoot(u); v = getRoot(v);
- if (u == v) return false;
- if (par[u] > par[v]) swap(u, v);
- par[u] += par[v]; par[v] = u;
- return true;
- }
- priority_queue<dataHeap, vector<dataHeap>, greater<dataHeap> > pq;
- int d[N][4], root[N][4];
- void Dijkstra1() {
- for (int i = 1; i <= n; ++i) for (int j = 1; j <= 2; ++j) d[i][j] = oo, root[i][j] = -1;
- for (int u : lisDoor) {
- d[u][1] = 0; root[u][1] = getRoot(u);
- pq.push(dataHeap(u, 1, d[u][1]));
- }
- while (pq.size()) {
- int u = pq.top().u, type = pq.top().type, val = pq.top().val; pq.pop();
- if (val != d[u][type]) continue;
- for (int i = 0; i < (int) adj[u].size(); ++i) {
- int v = adj[u][i].second, cost = adj[u][i].first;
- if (d[v][1] > val + cost) {
- d[v][1] = val + cost; root[v][1] = root[u][type];
- pq.push(dataHeap(v, 1, d[v][1]));
- }
- }
- }
- }
- void Dijkstra2() {
- for (int i = 1; i <= n; ++i) pq.push(dataHeap(i, 1, d[i][1]));
- while (pq.size()) {
- int u = pq.top().u, type = pq.top().type, val = pq.top().val; pq.pop();
- if (val != d[u][type]) continue;
- for (int i = 0; i < (int) adj[u].size(); ++i) {
- int v = adj[u][i].second, cost = adj[u][i].first;
- if (d[v][2] > val+cost && root[u][type] != root[v][1]) {
- d[v][2] = val+cost; root[v][2] = root[u][type];
- pq.push(dataHeap(v, 2, d[v][2]));
- }
- }
- }
- }
- vector<dataEdge> Edge;
- int Trace[N], best[N];
- void sol() {
- int Add = Min_Distance_To_Tree::Dijkstra(), res = 0;
- for (int i = 1; i <= n; ++i) par[i] = -1;
- while (true) {
- Dijkstra1(); Dijkstra2();
- for (int i = 1; i <= n; ++i) best[i] = oo, Trace[i] = -1;
- for (int ver : lisDoor) {
- int u = getRoot(ver), v = root[ver][2], w = d[ver][2];
- if (best[u] > w) { best[u] = w; Trace[u] = v; }
- if (best[v] > w) { best[v] = w; Trace[v] = v; }
- }
- Edge.clear();
- for (int ver : lisDoor) {
- int u = getRoot(ver);
- if (Trace[u] == -1) continue;
- int v = Trace[u], w = best[u];
- Edge.push_back(dataEdge(u, v, w));
- }
- sort(Edge.begin(), Edge.end());
- for (dataEdge foo : Edge) {
- int u = foo.u, v = foo.v, w = foo.w;
- if (Merge(u, v)) res += w;
- }
- int Count = 0;
- for (int i : lisDoor) Count += (par[i] < 0);
- if (Count == 1) break;
- }
- cout << res + Add << '\n';
- }
- #undef int
- int main() {
- #define int long long
- freopen("input.txt", "r", stdin);
- Read(n); Read(m);
- int u, v, w;
- for (int i = 1; i <= m; ++i) {
- Read(u); Read(v); Read(w);
- adj[u].push_back(ii(w, v)); adj[v].push_back(ii(w, u));
- }
- Read(numDoor);
- for (int i = 1; i <= numDoor; ++i) Read(u), lisDoor.push_back(u);
- sol();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement