#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, par[20][100005], mx[20][100005], dist[100005], dep[100005], vis[100005], pa[100005];
vector <pi> adj[100005];
vector <int> adj2[100005];
int P[100005];
int getr(int x){return pa[x] == x ? x : pa[x] = getr(pa[x]);}
void merge(int a, int b){
a = getr(a), b = getr(b);
if(a == b)return;
pa[b] = a;
}
bool cmp(int a, int b){
return dist[a] > dist[b];
}
void dfs(int x, int p, int d){
par[0][x] = p;
mx[0][x] = min(dist[x], (p == -1 ? (int)1e9 : dist[p]));
dep[x] = d;
for(auto i : adj2[x])if(i != p)dfs(i, x, d + 1);
}
int qry(int u, int v){
if(dep[u] > dep[v])swap(u, v);
int diff = dep[v] - dep[u];
int ans = min(dist[u], dist[v]);
for(int i = 0; i < 19; i++)if(diff >> i & 1)ans = min(ans, mx[i][v]), v = par[i][v];
if(u == v)return ans;
for(int i = 19; i >= 0; i--){
if(par[i][u] != par[i][v]){
ans = min({ans, mx[i][u], mx[i][v]});
u = par[i][u];
v = par[i][v];
}
}
return min({ans, mx[0][u], mx[0][v]});
}
void solve(){
cin >> n >> m;
while(m--){
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
for(int i=1;i<=n;i++)dist[i] = 1e18;
priority_queue <pi, vector <pi>, greater <pi> > pq;
int k; cin >> k;
while(k--){
int x; cin >> x;
pq.push({0, x});
dist[x] = 0;
}
while(!pq.empty()){
int x = pq.top().fi, y = pq.top().se;
pq.pop();
if(dist[y] < x)continue;
for(auto [i, j] : adj[y])if(dist[i] > x + j)dist[i] = x + j, pq.push({dist[i], i});
}
for(int i = 1; i <= n; i++)cout << dist[i] << ' ';
cout << '\n';
for(int i=1;i<=n;i++)P[i] = pa[i] = i;
sort(P+1, P+n+1, cmp);
for(int i=1;i<=n;i++){
vis[P[i]] =1;
for(auto [j, k] : adj[P[i]]){
if(vis[j]){
if(getr(j) != getr(P[i]))merge(j, P[i]), adj2[P[i]].push_back(j), adj2[j].push_back(P[i]);
}
}
}
dfs(1, -1, 1);
for(int i = 1; i <= 19; i++)for(int j = 1; j <= n; j++){
par[i][j] = par[i-1][par[i-1][j]];
mx[i][j] = min(mx[i-1][j], mx[i-1][par[i-1][j]]);
}
int q; cin >> q;
while(q--){
int a, b; cin >> a >> b;
cout << qry(a, b) << '\n';
}
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
plan.cpp:98:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
98 | main(){
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
39256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
39256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
39512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
163 ms |
58096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
39256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
