이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
int n,m,k,q;
vector<vector<pair<int,ll>>> a;
vi b;
vector<ll> dist;
int main() {
cin>>n>>m;
a.resize(n);
REP(i,0,m){
int x,y;ll z;
cin>>x>>y>>z;
x--;y--;
a[x].PB({y,z});
a[y].PB({x,z});
}
cin>>k;
b.resize(k);
REP(i,0,k)cin>>b[i];
REP(i,0,k)b[i]--;
dist.resize(n,INF);
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
REP(i,0,k){
dist[b[i]]=0;
pq.push({0,b[i]});
}
while(!pq.empty()){
ll d=pq.top().F;
int x=pq.top().S;
pq.pop();
if(d!=dist[x])continue;
for(auto u:a[x]){
if(dist[u.F]<=dist[x]+u.S)continue;
dist[u.F]=dist[x]+u.S;
pq.push({dist[u.F],u.F});
}
}
cin>>q;
while(q--){
int x,y;cin>>x>>y;
x--;y--;
cout<<min(dist[x],dist[y])<<"\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... |