#610676 (C++17) No.1442 I-wate Shortest Path Problem

提出ソース

結果

問題	No.1442 I-wate Shortest Path Problem
ユーザー	iaNTU
提出日時	2021-01-29 20:16:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,668 bytes
コンパイル時間	2,319 ms
コンパイル使用メモリ	211,324 KB
実行使用メモリ	33,232 KB
最終ジャッジ日時	2024-10-11 12:20:45
合計ジャッジ時間	11,865 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 6,912 KB
testcase_01	AC	7 ms 6,912 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	9 ms 6,656 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	22 ms 8,192 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	684 ms 27,404 KB
testcase_13	AC	221 ms 25,472 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	WA	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	AC	166 ms 31,492 KB
testcase_23	AC	1,019 ms 33,232 KB
testcase_24	AC	179 ms 25,596 KB
testcase_25	WA	-
testcase_26	AC	193 ms 26,776 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// Exported by Exporter.exe

// Included from A.cpp
// Compile flags -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define MTP make_tuple
typedef long long int ll;

constexpr int kN = int(1E5 + 10);
constexpr int kLgn = 17;
// constexpr int kMod = 998244353;
// constexpr int kInf = 0x3f3f3f3f;
// constexpr ll kInf = 0x3f3f3f3f3f3f3f3f;
// constexpr double kPi = acos(-1);
// constexpr double kEps = 1E-9;

template <typename T> T ABS(T n) {return n >= 0 ? n : -n;}


// Included from C:\Users\ianli\Desktop\CP\template\Various\Fast_IO.cpp
static inline char Get_Raw_Char() {
	static char buf[1 << 16], *p = buf, *end = buf;
	if (p == end) {
		if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';
		p = buf;
	}
	return *p++;
}

static inline int Get_Digit() {
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	return int(c - '0');
}

static inline int Get_PInt() {
	char c = Get_Raw_Char();
	int ret;
	while (!isdigit(c)) c = Get_Raw_Char();
	ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	return ret;
}

static inline int Get_Int() {
	char c = Get_Raw_Char();
	bool neg = false;
	int ret;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	if (neg) return -ret;
	return ret;
}

static inline long long int Get_ll() {
	char c = Get_Raw_Char();
	bool neg = false;
	long long int ret;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	if (neg) return -ret;
	return ret;
}

static inline long long int Get_Pll() {
	char c = Get_Raw_Char();
	long long int ret;
	while (!isdigit(c)) c = Get_Raw_Char();
	ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	return ret;
}

template <typename T> static inline void Read_P(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	return ;
}

template <typename T> static inline void Read(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	bool neg = false;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	if (neg) n = -n;
	return ;
}

template <typename T> static inline void Read_Digit(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	n = int(c - '0');
	return ;
}

template <typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {
	Read(n);
	return Read(Fargs...);
}

template <typename T, typename... Targs> static inline void Read_Digit(T &n, Targs&... Fargs) {
	Read_Digit(n);
	return Read_Digit(Fargs...);
}

template <typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {
	Read_P(n);
	return Read_P(Fargs...);
}
// End of C:\Users\ianli\Desktop\CP\template\Various\Fast_IO.cpp

int m[10], p[10], x[10][kN], u[kN], v[kN], dep[kN];
ll ans[kN], fa[kLgn][kN], dis[kN];
vector<pair<int, int>> graph[kN];
bitset<kN> went;

void dfs(int cur, int from) {
	for (pair<int, int> i : graph[cur]) if (i.F != from) {
		fa[0][i.F] = cur;
		dis[i.F] = dis[cur] + i.S;
		dep[i.F] = dep[cur] + 1;
		dfs(i.F, cur);
	}
	return ;
}

int LCA(int l, int r) {
	if (dep[l] < dep[r]) swap(l, r);
	for (int i = kLgn - 1; i >= 0; i--) if (dep[fa[i][l]] >= dep[r]) l = fa[i][l];
	if (l == r) return l;
	for (int i = kLgn - 1; i >= 0; i--) if (fa[i][l] != fa[i][r]) l = fa[i][l], r = fa[i][r];
	return fa[0][l];
}

int main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//freopen("file_name", "r", stdin);
	//freopen("file_name", "w", stdout);
	//fstream input, output;
	//input.open("file_name", ios::in);
	//output.open("file_name", ios::out);
	int n, k, q;
	scanf("%d%d", &n, &k);
	for (int i = 2; i <= n; i++) {
		int l, r, c;
		scanf("%d%d%d", &l, &r, &c);
		graph[l].PB(MP(r, c));
		graph[r].PB(MP(l, c));
	}
	for (int i = 1; i <= k; i++) {
		scanf("%d%d", &m[i], &p[i]);
		for (int j = 1; j <= m[i]; j++) scanf("%d", &x[i][j]);
	}

	scanf("%d", &q);
	for (int i = 1; i <= n; i++) scanf("%d%d", &u[i], &v[i]);

	// no special
	// could be done in O(n) (tarjan's LCA)
	dfs(1, 1);
	fa[0][1] = 1;
	for (int i = 1; i < kLgn; i++) for (int j = 1; j <= n; j++) fa[i][j] = fa[i - 1][fa[i - 1][j]];
	for (int i = 1; i <= q; i++) ans[i] = dis[u[i]] + dis[v[i]] - dis[LCA(u[i], v[i])] * 2;

	int tot = 1 << k;
	for (int mask = 1; mask < tot; mask++) {
		went.reset();
		memset(dis, 0x3f, sizeof(dis));

		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; // (dis, idx)
		ll tmp = 0;
		for (int i = 1; i <= k; i++) if (mask & (1 << (i - 1))) {
			for (int j = 1; j <= m[i]; j++) went[x[i][j]] = true;
			tmp += p[i];
		}
		for (int i = 1; i <= n; i++) if (went[i]) pq.push(MP(dis[i] = 0, i));

		while (!pq.empty()) {
			int cur = pq.top().S;
			ll ndis = pq.top().F;
			pq.pop();
			if (ndis > dis[cur]) continue;
			for (pair<int, int> i : graph[cur]) if (dis[i.F] > ndis + i.S) pq.push(MP(dis[i.F] = ndis + i.S, i.F));
		}
		
		for (int i = 1; i <= q; i++) ans[i] = min(ans[i], dis[u[i]] + dis[v[i]] + tmp);
	}


	for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);

	//input.close();
	//output.close();
}
// End of A.cpp

yukicoder

結果

テストケース

ソースコード