結果

問題 No.1442 I-wate Shortest Path Problem
ユーザー kwm_tkwm_t
提出日時 2021-03-31 20:39:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 502 ms / 3,000 ms
コード長 3,803 bytes
コンパイル時間 2,108 ms
コンパイル使用メモリ 185,516 KB
実行使用メモリ 45,884 KB
最終ジャッジ日時 2024-12-15 08:02:00
合計ジャッジ時間 9,613 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
8,384 KB
testcase_01 AC 4 ms
8,684 KB
testcase_02 AC 9 ms
9,848 KB
testcase_03 AC 39 ms
12,200 KB
testcase_04 AC 8 ms
9,600 KB
testcase_05 AC 7 ms
9,268 KB
testcase_06 AC 39 ms
12,224 KB
testcase_07 AC 6 ms
11,300 KB
testcase_08 AC 36 ms
9,360 KB
testcase_09 AC 13 ms
12,244 KB
testcase_10 AC 41 ms
13,296 KB
testcase_11 AC 42 ms
10,112 KB
testcase_12 AC 345 ms
39,132 KB
testcase_13 AC 194 ms
31,316 KB
testcase_14 AC 268 ms
37,728 KB
testcase_15 AC 242 ms
33,848 KB
testcase_16 AC 301 ms
38,060 KB
testcase_17 AC 468 ms
40,880 KB
testcase_18 AC 493 ms
40,976 KB
testcase_19 AC 395 ms
40,676 KB
testcase_20 AC 499 ms
40,908 KB
testcase_21 AC 502 ms
41,084 KB
testcase_22 AC 222 ms
36,824 KB
testcase_23 AC 431 ms
45,884 KB
testcase_24 AC 192 ms
33,280 KB
testcase_25 AC 359 ms
42,448 KB
testcase_26 AC 171 ms
34,428 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
//#include "atcoder/all"
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
typedef pair<long long, int> P;
class Tree {
public:
	Tree(int V, int root) : V(V), root(root) {
		T.resize(V);
		for (int i = 0; i < MAXLOGV; i++) parent[i].resize(V);
		depth.resize(V);
	}
	// uとvをつなぐ
	// lcaを求めることが主目的なので無向グラフとしている
	void unite(int u, int v) {
		T[u].push_back(v);
		T[v].push_back(u);
	}
	// initする
	// コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ
	void init() {
		dfs(root, -1, 0);
		for (int k = 0; k + 1 < MAXLOGV; k++) {
			for (int v = 0; v < V; v++) {
				if (parent[k][v] < 0) parent[k + 1][v] = -1;
				else parent[k + 1][v] = parent[k][parent[k][v]];
			}
		}
	}
	// uとvのlcaを求める
	int lca(int u, int v) const {
		if (depth[u] > depth[v]) swap(u, v);
		for (int k = 0; k < MAXLOGV; k++) {
			if ((depth[v] - depth[u]) >> k & 1) {
				v = parent[k][v];
			}
		}
		if (u == v) return u;
		for (int k = MAXLOGV - 1; k >= 0; k--) {
			if (parent[k][u] != parent[k][v]) {
				u = parent[k][u];
				v = parent[k][v];
			}
		}
		return parent[0][u];
	}
	// uとvの距離を求める
	// edgeを定義しないといけない時はこれじゃダメ
	int dist(int u, int v) const {
		int p = lca(u, v);
		return (depth[u] - depth[p]) + (depth[v] - depth[p]);
	}
	void dfs(int v, int p, int d) {
		parent[0][v] = p;
		depth[v] = d;
		for (int next : T[v]) {
			if (next != p) dfs(next, v, d + 1);
		}
	}
	static const int MAXLOGV = 25;
	// グラフの隣接リスト表現
	vector<vector<int> > T;
	// 頂点の数
	int V;
	// 根ノードの番号
	int root;

	// 親ノード
	vector<int> parent[MAXLOGV];
	// 根からの深さ
	vector<int> depth;
};
struct Edge {
	int to, cost;
	Edge(int _to, int _cost) :to(_to), cost(_cost) {}
};
vector<Edge>g0[100005];
vector<Edge>g[100015];
long long d[100005];
long long d2[10][100015];
void dfs(int v, int p = -1) {
	for (auto e : g0[v]) {
		if (p == e.to) { continue; }
		d[e.to] += d[v] + e.cost;
		dfs(e.to, v);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, K;
	cin >> N >> K;
	Tree tree(N, 0);
	rep(i, N - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		tree.unite(a, b);
		g0[a].emplace_back(b, c * 2);
		g0[b].emplace_back(a, c * 2);
		g[a].emplace_back(b, c * 2);
		g[b].emplace_back(a, c * 2);
	}
	rep(i, K) {
		int M, P;
		cin >> M >> P;
		rep(j, M) {
			int x;
			cin >> x;
			x--;
			g[x].emplace_back(i + N, P);
			g[i + N].emplace_back(x, P);
		}
	}
	rep(i, N + K) { rep(j, K) { d2[j][i] = LINF; } }
	rep(i, K) {
		priority_queue<P, vector<P>, greater<P> > q;//小さいもの順
		q.emplace(0, i + N);
		d2[i][i + N] = 0;
		while (!q.empty()) {
			auto tmp = q.top();
			q.pop();
			long long cost = tmp.first;
			long long pos = tmp.second;
			if (cost > d2[i][pos]) {
				continue;
			}
			for (Edge e : g[pos]) {
				if (cost + e.cost < d2[i][e.to]) {
					d2[i][e.to] = e.cost + cost;
					q.emplace(d2[i][e.to], e.to);
				}
			}
		}
	}
	tree.init();
	dfs(0);
	int Q;
	cin >> Q;
	while (Q--) {
		int U, V;
		cin >> U >> V;
		U--; V--;
		long long ans = d[U] + d[V] - 2 * d[tree.lca(U, V)];
		rep(i, K) {
			ans = min(ans, d2[i][U] + d2[i][V]);
		}
		ans /= 2;
		cout << ans << endl;
	}
	return 0;
}
0