結果
| 問題 |
No.1442 I-wate Shortest Path Problem
|
| コンテスト | |
| ユーザー |
 first_vil
|
| 提出日時 | 2021-03-26 16:12:44 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,396 bytes |
| コンパイル時間 | 2,820 ms |
| コンパイル使用メモリ | 60,412 KB |
| 最終ジャッジ日時 | 2025-01-19 21:47:01 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:81:10: fatal error: testlib.h: No such file or directory
81 | #include "testlib.h"
| ^~~~~~~~~~~
compilation terminated.
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
using graph = vector<VI>;
template<class T = ll> using w_graph = vector<vector<pair<int, T>>>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define eFOR(i,a,n) for(int i=(a);i<=(n);++i)
#define rFOR(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define erFOR(i,a,n) for(int i=(n);i>=(a);--i)
#define SORT(a) sort(a.begin(),a.end())
#define rSORT(a) sort(a.rbegin(),a.rend())
#define fSORT(a,f) sort(a.begin(),a.end(),f)
#define all(a) a.begin(),a.end()
#define out(y,x) ((y)<0||h<=(y)||(x)<0||w<=(x))
#define tp(a,i) get<i>(a)
#ifdef _DEBUG
#define line cout << "-----------------------------\n"
#define stop system("pause")
#endif
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T, class... Ts>inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline void print(const vector<vector<T>>& v) { for (auto& a : v)print(a); }
inline string reversed(const string& s) { string t = s; reverse(all(t)); return t; }
template<class T>inline T sum(const vector<T>& a, int l, int r) { return a[r] - (l == 0 ? 0 : a[l - 1]); }
template<class T>inline void END(T s) { print(s); exit(0); }
void END() { exit(0); }
class unionfind {
VI par, rank;
int forest_num;
public:
unionfind(const int& n) : par(n), rank(n, 1), forest_num(n) {
FOR(i, 0, n)par[i] = i;
}
int root(int x) {
if (par[x] == x)return x;
return par[x] = root(par[x]);
}
int size(int x) {
if (par[x] == x)return rank[x];
return size(par[x]);
}
void unite(int x, int y) {
int rx = root(x), ry = root(y);
if (rx == ry)return;
if (rank[rx] < rank[ry]) {
par[rx] = ry;
rank[ry] += rank[rx];
}
else {
par[ry] = rx;
rank[rx] += rank[ry];
}
--forest_num;
}
bool same(int x, int y) { return root(x) == root(y); }
int fnum() { return forest_num; }
};
#include "testlib.h"
int main() {
init();
registerValidation();
int n = inf.readInt(2, 100000);
inf.readSpace();
int k = inf.readInt(0, 10);
inf.readEoln();
w_graph<int> g(n + k);
unionfind uf(n);
FOR(i, 0, n - 1) {
int a = inf.readInt(1, n - 1);
inf.readSpace();
int b = inf.readInt(a + 1, n);
inf.readSpace();
int c = inf.readInt(1, INF);
inf.readEoln();
--a, --b;
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
uf.unite(a, b);
}
assert(uf.size(0) == n);
VI dep(n);
VL lca_dis(n);
auto nxt = defvec<int>(-1, 18, n);
auto dfs = [&](auto&& f, int cur, int par)->void {
for (auto [to, cost] : g[cur]) {
if (to != par) {
dep[to] = dep[cur] + 1;
lca_dis[to] = lca_dis[cur] + cost;
nxt[0][to] = cur;
f(f, to, cur);
}
}
};
dfs(dfs, 0, -1);
FOR(j, 0, 17)FOR(i, 0, n) {
if (nxt[j][i] != -1)nxt[j + 1][i] = nxt[j][nxt[j][i]];
}
auto lca = [&](int a, int b)->int {
if (dep[a] > dep[b])swap(a, b);
int d = dep[b] - dep[a];
rFOR(j, 0, 18)if (d >> j & 1)b = nxt[j][b];
if (a == b)return a;
rFOR(j, 0, 18)if (nxt[j][a] != nxt[j][b]) {
a = nxt[j][a], b = nxt[j][b];
}
return nxt[0][a];
};
int m_sum = 0;
VI p(k);
set<int> s;
FOR(i, 0, k) {
s.clear();
int m = inf.readInt(2, n);
inf.readSpace();
p[i] = inf.readInt(1, INF);
inf.readEoln();
m_sum += m;
FOR(j, 0, m) {
if (j)inf.readSpace();
int x = inf.readInt(1, n);
--x;
g[n + i].emplace_back(x, 0);
g[x].emplace_back(n + i, p[i]);
s.insert(x);
}
inf.readEoln();
assert(s.size() == m);
}
assert(m_sum <= 100000);
auto dp = defvec<ll>(LLINF, k, n + k);
PQ<pair<ll, int>> dik;
FOR(j, 0, k) {
dp[j][n + j] = 0;
dik.emplace(0, n + j);
while (!dik.empty()) {
auto [d, cur] = dik.top();
dik.pop();
if (dp[j][cur] < d)continue;
for (auto [to, cost] : g[cur]) {
if (!chmin(dp[j][to], d + cost))continue;
dik.emplace(d + cost, to);
}
}
}
int q = inf.readInt(1, 100000);
inf.readEoln();
FOR(_, 0, q) {
int u = inf.readInt(1, n - 1);
inf.readSpace();
int v = inf.readInt(u + 1, n);
inf.readEoln();
--u, --v;
ll ans = lca_dis[u] + lca_dis[v] - 2 * lca_dis[lca(u, v)];
FOR(j, 0, k)chmin(ans, dp[j][u] + dp[j][v] + p[j]);
print(ans);
}
inf.readEof();
return 0;
}