Submission #2557060

---

Source Code Expand

import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int n; readV(n);

  auto g = GraphW!(int, long)(n);
  foreach (_; 0..n-1) {
    int a, b, c; readV(a, b, c); --a; --b;
    g.addEdgeB(a, b, c);
  }

  int q, k; readV(q, k); --k;

  auto d = new long[](n), vst = new bool[](n);

  struct VD { int v; long d; }
  auto qu = DList!int(k);
  vst[k] = true;

  while (!qu.empty) {
    auto v = qu.front; qu.removeFront();
    foreach (e; g[v].filter!(e => !vst[e.dst])) {
      d[e.dst] = d[v] + e.wt;
      vst[e.dst] = true;
      qu.insertBack(e.dst);
    }
  }

  foreach (_; 0..q) {
    int x, y; readV(x, y); --x; --y;
    writeln(d[x]+d[y]);
  }
}

struct GraphW(N = int, W = int, W i = 10^^9)
{
  alias Node = N, Wt = W, inf = i;
  struct Edge { Node src, dst; Wt wt; alias cap = wt; }
  Node n;
  Edge[][] g;
  alias g this;
  this(Node n) { this.n = n; g = new Edge[][](n); }
  void addEdge(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); }
  void addEdgeB(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); g[v] ~= Edge(v, u, w); }
}

Submission Info

Judge Result