Language: C++

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1 << 29)#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1 << 29)
typedef pair<long long , long long > EDGE;
typedef pair<long long , EDGE> COST;

vector<EDGE> edge[100100], edges;
long long  dist[100100];
long long  parents[100100][29];
long long  minimum[100100][29];
long long  depth[100100];
long long  u[100100];
long long  k, f, n, m, a, b, l, s, t, q;
void dijkstra(){//fill dist
  priority_queue<pair<long long, long long> ,vector<pair<long long, long long> >, greater<pair<long long, long long> > > pq;
  for(long long  i = 0;i < k;i++){
    cin >> f;
    dist[f] = 0;
    pq.push(make_pair(0, f));
  }
  while(!pq.empty()){
    pair<long long , long long> tmp = pq.top();pq.pop();
    long long  node = tmp.second;
    if(dist[node] < tmp.first)continue;
    for(long long  i = 0;i < edge[node].size();i++){
      if(dist[edge[node][i].first] > edge[node][i].second + dist[node]){
	dist[edge[node][i].first] = edge[node][i].second + dist[node];
	pq.push(make_pair(dist[edge[node][i].first], edge[node][i].first));
      }
    }
  }
}



long long  unin(long long  x){
  if(u[x] == x)return x;
  return u[x] = unin(u[x]);
}

void unite(long long  a, long long  b){
  a = unin(a);
  b = unin(b);
  u[b] = a;
}

void ddfs(long long  x, long long  d, long long  last){
  depth[x] = d;
  parents[x][0] = last;
  if(last != -INF)  minimum[x][0] = min(dist[x], dist[last]);
  else minimum[x][0] = -INF;
  for(long long  i = 0;i < edge[x].size();i++){
    if(edge[x][i].first == last)continue;
    ddfs(edge[x][i].first, d + 1, x);
  }
}

void make_tree(){
  priority_queue<COST> pq;
  for(long long  i = 0;i <= n;i++)edge[i].clear();
  for(long long  i = 0;i < edges.size();i++){
    long long  a = edges[i].first, b = edges[i].second;
    pq.push(COST(max(dist[a], dist[b]), edges[i]));
  }
  for(long long  i = 1;i <= n;i++)u[i] = i;
  while(!pq.empty()){
    COST tmp = pq.top();pq.pop();
    long long  a = tmp.second.first, b = tmp.second.second;
    if(unin(a) == unin(b))continue;
    edge[a].push_back(EDGE(b, tmp.first));
    edge[b].push_back(EDGE(a, tmp.first));
    unite(a, b);
  }
  ddfs(1, 0, -INF);//fill depth and parents[i][0]
  for(long long  i = 1;i <= 30;i++){
    for(long long  j = 0;j <= n;j++){
      if(parents[j][i - 1] != -INF){
	parents[j][i] = parents[parents[j][i - 1]][i - 1];
	minimum[j][i] = min(minimum[j][i - 1], minimum[parents[j][i - 1]][i - 1]);
      }
      else{
	parents[j][i] = -INF;
	minimum[j][i] = -INF;
      }
    }
  }
}

long long  above(long long  x, long long  d, long long  r){
  if(x == -INF)return -INF;
  if(d == 0)return x;
  while((1 << r) > d)r--;
  return above(parents[x][r], d - (1 << r), r);
}

long long  mini(long long  x, long long  d, long long  r){
  if(d == 0)return dist[x];
  while((1 << r) > d)r--;
  return min(minimum[x][r], mini(parents[x][r], d - (1 << r), r));
}

long long  solve(long long  a, long long  b){
  long long  res;
  if(depth[a] < depth[b])swap(a, b);
  res = mini(a, depth[a] - depth[b], 30);
  a = above(a, depth[a] - depth[b], 30);
  if(a == b)return res;
  long long  top = 100100, bottom = 0;
  while(top - bottom > 1){
    long long  mid = (top + bottom) / 2;
    if(above(a, mid, 30) == above(b, mid, 30))
      top = mid;
    else
      bottom = mid;
  }

  res = min(res, mini(a, top, 30));
  res = min(res, mini(b, top, 30));
  return res;
}

int  main(){
  fill(dist, dist + 105000, INF);
  cin >> n >> m >> k >> q;
  for(long long  i = 0;i < m;i++){
    cin >> a >> b >> l;
    edge[a].push_back(EDGE(b,l));
    edge[b].push_back(EDGE(a,l));
    edges.push_back(EDGE(a,b));
  }
  dijkstra();
  make_tree();
  for(long long  i = 0;i < q;i++){
    cin >> s >> t;
    cout << solve(s, t) << endl;
  }
  return 0;
}


/*
       9
0  5        7   0 
       10

0

5

10

7

0    9

 */
typedef pair<long long , long long > EDGE;
typedef pair<long long , EDGE> COST;

vector<EDGE> edge[100100], edges;
long long  dist[100100];
long long  parents[100100][31];
long long  minimum[100100][31];
long long  depth[100100];
long long  u[100100];
long long  k, f, n, m, a, b, l, s, t, q;
void dijkstra(){//fill dist
  priority_queue<pair<long long, long long> ,vector<pair<long long, long long> >, greater<pair<long long, long long> > > pq;
  for(long long  i = 0;i < k;i++){
    cin >> f;
    dist[f] = 0;
    pq.push(make_pair(0, f));
  }
  while(!pq.empty()){
    pair<long long , long long> tmp = pq.top();pq.pop();
    long long  node = tmp.second;
    if(dist[node] < tmp.first)continue;
    for(long long  i = 0;i < edge[node].size();i++){
      if(dist[edge[node][i].first] > edge[node][i].second + dist[node]){
	dist[edge[node][i].first] = edge[node][i].second + dist[node];
	pq.push(make_pair(dist[edge[node][i].first], edge[node][i].first));
      }
    }
  }
}



long long  unin(long long  x){
  if(u[x] == x)return x;
  return u[x] = unin(u[x]);
}

void unite(long long  a, long long  b){
  a = unin(a);
  b = unin(b);
  u[b] = a;
}

void ddfs(long long  x, long long  d, long long  last){
  depth[x] = d;
  parents[x][0] = last;
  if(last != -INF)  minimum[x][0] = min(dist[x], dist[last]);
  else minimum[x][0] = -INF;
  for(long long  i = 0;i < edge[x].size();i++){
    if(edge[x][i].first == last)continue;
    ddfs(edge[x][i].first, d + 1, x);
  }
}

void make_tree(){
  priority_queue<COST> pq;
  for(long long  i = 0;i <= n;i++)edge[i].clear();
  for(long long  i = 0;i < edges.size();i++){
    long long  a = edges[i].first, b = edges[i].second;
    pq.push(COST(max(dist[a], dist[b]), edges[i]));
  }
  for(long long  i = 1;i <= n;i++)u[i] = i;
  while(!pq.empty()){
    COST tmp = pq.top();pq.pop();
    long long  a = tmp.second.first, b = tmp.second.second;
    if(unin(a) == unin(b))continue;
    edge[a].push_back(EDGE(b, tmp.first));
    edge[b].push_back(EDGE(a, tmp.first));
    unite(a, b);
  }
  ddfs(1, 0, -INF);//fill depth and parents[i][0]
  for(long long  i = 1;i <= 30;i++){
    for(long long  j = 0;j <= n;j++){
      if(parents[j][i - 1] != -INF){
	parents[j][i] = parents[parents[j][i - 1]][i - 1];
	minimum[j][i] = min(minimum[j][i - 1], minimum[parents[j][i - 1]][i - 1]);
      }
      else{
	parents[j][i] = -INF;
	minimum[j][i] = -INF;
      }
    }
  }
}

long long  above(long long  x, long long  d, long long  r){
  if(x == -INF)return -INF;
  if(d == 0)return x;
  while((1 << r) > d)r--;
  return above(parents[x][r], d - (1 << r), r);
}

long long  mini(long long  x, long long  d, long long  r){
  if(d == 0)return dist[x];
  while((1 << r) > d)r--;
  return min(minimum[x][r], mini(parents[x][r], d - (1 << r), r));
}

long long  solve(long long  a, long long  b){
  long long  res;
  if(depth[a] < depth[b])swap(a, b);
  res = mini(a, depth[a] - depth[b], 30);
  a = above(a, depth[a] - depth[b], 30);
  if(a == b)return res;
  long long  top = 100100, bottom = 0;
  while(top - bottom > 1){
    long long  mid = (top + bottom) / 2;
    if(above(a, mid, 30) == above(b, mid, 30))
      top = mid;
    else
      bottom = mid;
  }

  res = min(res, mini(a, top, 30));
  res = min(res, mini(b, top, 30));
  return res;
}

int  main(){
  fill(dist, dist + 105000, INF);
  cin >> n >> m >> k >> q;
  for(long long  i = 0;i < m;i++){
    cin >> a >> b >> l;
    edge[a].push_back(EDGE(b,l));
    edge[b].push_back(EDGE(a,l));
    edges.push_back(EDGE(a,b));
  }
  dijkstra();
  make_tree();
  for(long long  i = 0;i < q;i++){
    cin >> s >> t;
    cout << solve(s, t) << endl;
  }
  return 0;
}


/*
       9
0  5        7   0 
       10

0

5

10

7

0    9

 */

Compiler output:
a.cc:11:9: warning: "INF" redefined
   11 | #define INF (1 << 29)
      |         ^~~
a.cc:6:9: note: this is the location of the previous definition
    6 | #define INF (1 << 29)#include<iostream>
      |         ^~~
a.cc:168:14: error: redefinition of 'std::vector<std::pair<long long int, long long int> > edge [100100]'
  168 | vector<EDGE> edge[100100], edges;
      |              ^~~~
a.cc:15:14: note: 'std::vector<std::pair<long long int, long long int> > edge [100100]' previously declared here
   15 | vector<EDGE> edge[100100], edges;
      |              ^~~~
a.cc:168:28: error: redefinition of 'std::vector<std::pair<long long int, long long int> > edges'
  168 | vector<EDGE> edge[100100], edges;
      |                            ^~~~~
a.cc:15:28: note: 'std::vector<std::pair<long long int, long long int> > edges' previously declared here
   15 | vector<EDGE> edge[100100], edges;
      |                            ^~~~~
a.cc:169:12: error: redefinition of 'long long int dist [100100]'
  169 | long long  dist[100100];
      |            ^~~~
a.cc:16:12: note: 'long long int dist [100100]' previously declared here
   16 | long long  dist[100100];
      |            ^~~~
a.cc:170:12: error: conflicting declaration 'long long int parents [100100][31]'
  170 | long long  parents[100100][31];
      |            ^~~~~~~
a.cc:17:12: note: previous declaration as 'long long int parents [100100][29]'
   17 | long long  parents[100100][29];
      |            ^~~~~~~
a.cc:171:12: error: conflicting declaration 'long long int minimum [100100][31]'
  171 | long long  minimum[100100][31];
      |            ^~~~~~~
a.cc:18:12: note: previous declaration as 'long long int minimum [100100][29]'
   18 | long long  minimum[100100][29];
      |            ^~~~~~~
a.cc:172:12: error: redefinition of 'long long int depth [100100]'
  172 | long long  depth[100100];
      |            ^~~~~
a.cc:19:12: note: 'long long int depth [100100]' previously declared here
   19 | long long  depth[100100];
      |            ^~~~~
a.cc:173:12: error: redefinition of 'long long int u [100100]'
  173 | long long  u[100100];
      |            ^
a.cc:20:12: note: 'long long int u [100100]' previously declared here
   20 | long long  u[100100];
      |            ^
a.cc:174:12: error: redefinition of 'long long int k'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |            ^
a.cc:21:12: note: 'long long int k' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |            ^
a.cc:174:15: error: redefinition of 'long long int f'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |               ^
a.cc:21:15: note: 'long long int f' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |               ^
a.cc:174:18: error: redefinition of 'long long int n'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |                  ^
a.cc:21:18: note: 'long long int n' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |                  ^
a.cc:174:21: error: redefinition of 'long long int m'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |                     ^
a.cc:21:21: note: 'long long int m' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |                     ^
a.cc:174:24: error: redefinition of 'long long int a'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |                        ^
a.cc:21:24: note: 'long long int a' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |                        ^
a.cc:174:27: error: redefinition of 'long long int b'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |                           ^
a.cc:21:27: note: 'long long int b' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |                           ^
a.cc:174:30: error: redefinition of 'long long int l'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |                              ^
a.cc:21:30: note: 'long long int l' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |                              ^
a.cc:174:33: error: redefinition of 'long long int s'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |                                 ^
a.cc:21:33: note: 'long long int s' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |                                 ^
a.cc:174:36: error: redefinition of 'long long int t'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |                                    ^
a.cc:21:36: note: 'long long int t' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |                                    ^
a.cc:174:39: error: redefinition of 'long long int q'
  174 | long long  k, f, n, m, a, b, l, s, t, q;
      |                                       ^
a.cc:21:39: note: 'long long int q' previously declared here
   21 | long long  k, f, n, m, a, b, l, s, t, q;
      |                                       ^
a.cc:175:6: error: redefinition of 'void dijkstra()'
  175 | void dijkstra(){//fill dist
      |      ^~~~~~~~
a.cc:22:6: note: 'void dijkstra()' previously defined here
   22 | void dijkstra(){//fill dist
      |      ^~~~~~~~
a.cc:197:12: error: redefinition of 'long long int unin(long long int)'
  197 | long long  unin(long long  x){
      |            ^~~~
a.cc:44:12: note: 'long long int unin(long long int)' previously defined here
   44 | long long  unin(long long  x){
      |            ^~~~
a.cc:202:6: error: redefinition of 'void unite(long long int, long long int)'
  202 | void unite(long long  a, long long  b){
      |      ^~~~~
a.cc:49:6: note: 'void unite(long long int, long long int)' previously defined here
   49 | void unite(long long  a, long long  b){
      |      ^~~~~
a.cc:208:6: error: redefinition of 'void ddfs(long long int, long long int, long long int)'
  208 | void ddfs(long long  x, long long  d, long long  last){
      |      ^~~~
a.cc:55:6: note: 'void ddfs(long long int, long long int, long long int)' previously defined here
   55 | void ddfs(long long  x, long long  d, long long  last){
      |      ^~~~
a.cc:219:6: error: redefinition of 'void make_tree()'
  219 | void make_tree(){
      |      ^~~~~~~~~
a.cc:66:6: note: 'void make_tree()' previously defined here
   66 | void make_tree(){
      |      ^~~~~~~~~
a.cc:250:12: error: redefinition of 'long long int above(long long int, long long int, long long int)'
  250 | long long  above(long long  x, long long  d, long long  r){
      |            ^~~~~
a.cc:97:12: note: 'long long int above(long long int, long long int, long long int)' previously defined here
   97 | long long  above(long long  x, long long  d, long long  r){
      |            ^~~~~
a.cc:257:12: error: redefinition of 'long long int mini(long long int, long long int, long long int)'
  257 | long long  mini(long long  x, long long  d, long long  r){
      |            ^~~~
a.cc:104:12: note: 'long long int mini(long long int, long long int, long long int)' previously defined here
  104 | long long  mini(long long  x, long long  d, long long  r){
      |            ^~~~
a.cc:263:12: error: redefinition of 'long long int solve(long long int, long long int)'
  263 | long long  solve(long long  a, long long  b){
      |            ^~~~~
a.cc:110:12: note: 'long long int solve(long long int, long long int)' previously defined here
  110 | long long  solve(long long  a, long long  b){
      |            ^~~~~
a.cc:283:6: error: redefinition of 'int main()'
  283 | int  main(){
      |      ^~~~
a.cc:130:6: note: 'int main()' previously defined here
  130 | int  main(){
      |      ^~~~