이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # define int long long
# define fi first
# define se second
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
// const int INF = 1e18;
vector < pair < int, int > > adj[N];
vector < int > adj1[N];
int d[N], timer = 1, tin[N], tout[N], up[N][35], L, used[N], used1[N], t[4 * N], invtin[N];
void dfs( int v, int prv ) {
up[v][0] = prv;
used1[v] = 1;
invtin[timer] = v;
tin[v] = timer++;
for ( int i = 1; i <= L; i++ ) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
// cout << v << ' ' << d[v] << endl;
for ( auto u: adj1[v] ) {
if ( u != prv ) {
dfs(u, v);
}
}
tout[v] = timer;
}
set < pair < int, int > > ST;
void rec( int v ) {
used[v] = 1;
for ( auto pr: adj[v] ) {
int u = pr.fi;
if ( !used[u] ) {
ST.insert( {-d[u], u} );
}
}
if ( !ST.empty() ) {
int x = ST.begin()->se;
adj1[v].push_back(x);
adj1[x].push_back(v);
ST.erase(ST.begin());
rec( x );
}
}
bool is_ancestor( int u, int v ) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca( int u, int v ) {
if ( is_ancestor(u, v) ) {
return u;
}
if ( is_ancestor(v, u) ) {
return v;
}
for ( int i = L; i >= 0; i-- ) {
if ( is_ancestor( up[v][i], u ) ) {
v = up[v][i];
}
}
return up[v][0];
}
void build( int v, int l, int r ) {
if ( l == r ) {
t[v] = d[ invtin[l] ];
}
else {
int m = (l + r) / 2;
build( v * 2, l, m );
build( v * 2 + 1, m + 1, r );
t[v] = min( t[v * 2], t[v * 2 + 1] );
}
}
// int get( int v, int l, int )
int32_t main() {
speed;
int n, m;
cin >> n >> m;
L = log2(n) + 1;
for ( int i = 1; i <= m; i++ ) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int k;
cin >> k;
set < pair < int, int > > st;
for ( int i = 1; i <= n; i++ ) {
d[i] = mod;
}
for ( int i = 1; i <= k; i++ ) {
int x;
cin >> x;
d[x] = 0;
st.insert({0, x});
}
while ( !st.empty() ) {
int v = st.begin()->se;
st.erase( { d[v], v } );
// cout << v << " " << d[v] << endl;
for ( auto pr: adj[v] ) {
int u = pr.fi, w = pr.se;
if ( d[v] + w < d[u] ) {
st.erase( { d[u], u } );
d[u] = d[v] + w;
st.insert( { d[u], u } );
}
}
}
rec( 1 );
dfs(1, 1);
build( 1, 1, n );
int q;
cin >> q;
for ( int i = 1; i <= q; i++ ) {
int a, b;
cin >> a >> b;
int lc = lca(a, b), mn = d[lc];
while ( a != lc ) {
mn = min( mn, d[a] );
a = up[a][0];
}
while ( b != lc ) {
mn = min( mn, d[b] );
b = up[b][0];
}
cout << mn << '\n';
}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |