#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define int long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 1e5 + 9 , mod = 1e9 + 7;
ll a[N];
ll n , m , q , k;
vector<pair<int,int>>v[N];
set<pair<int,int>>st;
void dijkstra(){
while(st.size()){
auto it = st.begin();
ll x = it->se;
ll y = it->fi;
st.erase(it);
if(a[x] != y)
continue;
for(auto to : v[x]){
if(a[x] + to.se < a[to.fi]){
a[to.fi] = a[x] + to.se;
st.insert({a[to.fi] , to.fi});
}
}
}
}
ll sz[N] , p[N] , mn[N];
int get(int n) {
while(p[n] != n)
n = p[n];
return n;
}
void join(int x , int y , int k){
x = get(x);
y = get(y);
if(x != y){
if(sz[x] < sz[y])
swap(x , y);
p[y] = x;
mn[y] = k;
sz[x] += sz[y];
}
}
void get1(int x , int y){
ll ans = 1e15;
while(true){
if((sz[p[x]] < sz[p[y]]) || (p[y] == y)){
ans = min(ans , mn[x]);
x = p[x];
}else{
ans = min(ans , mn[y]);
y = p[y];
}
if(x == y){
ans = min(ans , a[x]);
break;
}
}
cout<<ans<<"\n";
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= m; i++){
int x , y , z;
cin>>x>>y>>z;
v[x].pb({y , z});
v[y].pb({x , z});
}
cin>>k;
for(int i = 1; i <= n; i++){
a[i] = 1e15;
}
while(k--){
int x;
cin>>x;
a[x] = 0;
st.insert({0 , x});
}
dijkstra();
vector<pair<int,int>>g;
for(int i = 1; i <= n; i++){
p[i] = i;
sz[i] = 1;
g.push_back({a[i] , i});
}
sort(rall(g));
for(auto i : g){
for(auto to : v[i.se]){
if(a[to.fi] >= a[i.se]){
join(i.se , to.fi , a[i.se]);
}
}
}
cin>>q;
while(q--){
int x , y;
cin>>x>>y;
get1(x , y);
}
}
signed main(){
TL;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1;
//cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
Compilation message
plan.cpp: In function 'long long int get(long long int)':
plan.cpp:49:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
49 | while(p[n] != n)
| ^~~~~
plan.cpp:51:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
51 | return n;
| ^~~~~~
plan.cpp: In function 'int main()':
plan.cpp:129:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:130:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
