이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define Kultivator ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int LL
using namespace std;
const LL Mxn = 1e6 + 7;
const LL Mod = 1e9 + 7;
const LL Inf = 1e14 + 7;
int N, M;
int d[100002], p[100002];
vector<pair<int, int>> g[100002];
map <pair <int, int>, bool> F;
priority_queue<pair<int, int>> q;
signed main(){
Kultivator;
cin >> N >> M;
for(int i = 1; i <= M; i++){
int A, B, W;
cin >> A >> B >> W;
g[A].pb({B, W});
g[B].pb({A, W});
F[{min(A, B), max(A, B)}] = true;
}
for (int i = 1; i <= N; i++) d[i] = 100000000 + 69;
int K;
cin >> K;
for(int i = 1; i <= K; i++){
int X;
cin >> X;
d[X] = false;
q.push({0, X});
}
while(!q.empty()){
int v = q.top().second;
q.pop();
for(auto to : g[v]){
if(to.second + d[v] < d[to.first]){
d[to.first] = to.second + d[v];
q.push({-d[to.first], to.first});
}
}
}
int Q;
cin >> Q;
while(Q--){
int s, t;
cin >> s >> t;
if (F[{min(s, t), max(s, t)}]) {
cout << min(d[s], d[t]) << '\n';
continue;
}
for (int i = 1; i <= N; i++) p[i] = -1000000;
p[s] = d[s];
q.push({p[s], s});
while(!q.empty()){
int v = q.top().second;
q.pop();
for(auto to : g[v]){
if(min(d[to.first], p[v]) > p[to.first]){
p[to.first] = min(d[to.first], p[v]);
q.push({ p[to.first], to.first });
}
}
}
cout << p[t] << '\n';
}
}
# | 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... |