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 "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
const int maxn = 100005;
using ll = long long;
vector<pair<int, ll>> edges[maxn];
ll dis[maxn][2];
bool vis[maxn];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i = 0; i < M; ++i){
edges[R[i][0]].push_back(make_pair(R[i][1], L[i]));
edges[R[i][1]].push_back(make_pair(R[i][0], L[i]));
}
using pii = pair<ll, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
memset(dis, 63, sizeof dis);
for(int i = 0; i < K; ++i){
pq.push(make_pair(0, P[i]));
dis[P[i]][0] = dis[P[i]][1] = 0;
}
while(!pq.empty()){
pii s = pq.top();
pq.pop();
if(vis[s.second])continue;
vis[s.second] = 1;
for(auto i : edges[s.second]){
ll cost = dis[s.second][1] + i.second;
if(dis[i.first][0] >= cost){
dis[i.first][1] = dis[i.first][0];
dis[i.first][0] = cost;
pq.push(make_pair(dis[i.first][1], i.first));
}else if(dis[i.first][1] > cost){
dis[i.first][1] = cost;
pq.push(make_pair(dis[i.first][1], i.first));
}
}
}
return dis[0][1];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |