This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/** kutbilim.one **/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
#define endl '\n'
/*
ifstream in("test.txt");
#define cin in */
vector< vector<pair<int, int>> > g;
vector<int> used, rad, dist;
int n, m;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
g.resize(1+n);
dist.assign(1+n, INT_MAX);
rad.assign(1+n, 0);
used.assign(1+n, 0);
int v[m], u[m], w[m];
for(int i = 0; i < m; i++){
cin >> v[i] >> u[i] >> w[i];
g[v[i]].push_back({u[i], w[i]});
g[u[i]].push_back({v[i], w[i]});
}
priority_queue<pair<int,int>> q;
int k;
cin >> k;
for(int i = 0; i < k; i++){
int a; cin >> a;
dist[a] = 0;
q.push({0,a});
}
while(!q.empty()) {
int a = q.top().second; q.pop();
if (used[a]) continue;
used[a] = true;
for(auto u : g[a]){
int b = u.first, wi = u.second;
if(dist[a]+wi < dist[b]){
dist[b] = min(dist[b], dist[a]+wi);
q.push({-dist[b], b});
}
}
}
/*
g.resize(1+n);
for(int i = 0; i < m; i++){
g[v[i]].push_back({u[i], dist[u[i]]});
g[u[i]].push_back({v[i], dist[v[i]]});
}
vector< vector<int> > dis(n, vector<int>(n, 0));
for(int i = 1; i <= n; i++){
fill(all(used), 0);
q.push({0, i});
while(!q.empty()){
int a = q.top().second; q.pop();
if(used[a]) continue;
used[a] = true;
for(auto u : g[a]){
int b = u.first, wi = u.second;
if(dis[i][a]+wi > dis[i][b]){
dis[i][b] = dis[i][a]+wi;
q.push({-dis[i][b], b});
}
}
}
for(int j = 1; j <= n; j++){
cout << dis[i][j] << " ";
}
cout << endl;
}
*/
int Q;
cin >> Q;
while(Q--){
int s, t;
cin >> s >> t;
cout << min(dist[s],dist[t]) << endl;
}
return 0;
}
# | 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... |