This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
ll a[100001];
ll ans=0,cnt=0,k=0;
const ll INF=1e18;
long long d[100100];
vector < pair<ll, ll> > g[100100];
ll p[100100];
vector <ll> vt[1001];
int main()
{
ll n,m;
cin >> n >> m;
for(int i=1;i<=m;i++){
ll x,y,w;
cin >> x >> y >> w;
g[x].push_back({y,w});
g[y].push_back({x,w});
}
ll k;
cin >> k;
ll b[k+1];
for(int i=1;i<=k;i++)
{
cin >> b[i];
}
ll op;
cin >> op;
pair <ll,ll> pr[op+1];
for(int i=1;i<=op;i++)
{
cin >> pr[i].first >> pr[i].second;
}
for(int qp = 1;qp<=k;qp++)
{
for(int i = 1; i <= n; i++) d[i] = INF;
ll s = b[qp];
d[s] = 0;
set < pair<long long,ll> > q;
q.insert (make_pair (d[s], s));
while (!q.empty()) {
int v = q.begin()->second;
q.erase (q.begin());
for (size_t j=0; j<g[v].size(); ++j) {
int to = g[v][j].first,
len = g[v][j].second;
if (d[v] + len < d[to]) {
q.erase (make_pair (d[to], to));
d[to] = d[v] + len;
p[to] = v;
q.insert (make_pair (d[to], to));
}
}
}
for(int pp = 1;pp<=op;pp++)
{
vt[pp].push_back(d[pr[pp].second]);
vt[pp].push_back(d[pr[pp].first]);
}
}
for(int i=0;i<=op;i++)
{
sort(vt[i].begin(),vt[i].end());
}
for(int i=0;i<=op;i++)
{
cout << vt[i][0];
cout << endl;
}
}
# | 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... |