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>
#include <fstream>
#define endl '\n'
#define mod 32768
#define INF 100000000000000
//#define ll long long
//#define cin fin
//#define cout fout
using namespace std;
//ofstream fout("convention.out");
//ifstream fin("convention.in");
const int M = 1e5 + 5;
long long arr[M];
vector<pair<int,long long>> v[M];
void d(int s)
{
for(int i = 0; i < M; i++)
{
arr[i] = INF;
}
arr[s] = 0;
priority_queue<pair<long long,int>, vector<pair<long long, int>>, greater<pair<long long,int>>> pq;
pq.push({arr[s],s});
while(!pq.empty())
{
pair<long long,int> tp = pq.top();
pq.pop();
if(arr[tp.second] < tp.first)
continue;
for(auto i : v[tp.second])
{
if(arr[tp.second]+i.second < arr[i.first])
{
arr[i.first] = arr[tp.second]+i.second;
pq.push({arr[i.first],i.first});
}
}
}
}
int main()
{
int n, m, k, q;
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
cin >> k;
int a[k];
for(int i = 0; i < k; i++)
{
cin >> a[i];
v[0].push_back({a[i],0});
v[a[i]].push_back({0,0});
}
d(0);
cin >> q;
while(q--)
{
int s, t;
cin >> s >> t;
cout << min(arr[s],arr[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... |