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;
typedef long long ll;
struct edge
{
int to;
int w;
};
vector<edge> adjList[100005];
int first[100005]; //Shortest path to that node from an exit
int second[100005]; //Second shortest path to that node from an exit
struct node
{
int data;
int key;
};
bool operator<(const node& a,const node& b)
{
return a.key<b.key;
}
priority_queue<node> Q;
void relax(int u,int v,int w)
{
if(second[u]+w<first[v]){
second[v]=first[v];
first[v]=second[u]+w;
node x={v,second[v]};
Q.push(x);
}
else if(second[u]+w<second[v]){
second[v]=second[u]+w;
node x={v,second[v]};
Q.push(x);
}
}
void dijkstra(int n,int k,int P[])
{
for(int i=0;i<n;i++){
first[i]=second[i]=INT_MAX;
}
for(int i=0;i<k;i++){
int u=P[i];
first[u]=second[u]=0;
node x={u,0};
Q.push(x);
}
while(Q.size()){
node u=Q.top();Q.pop();
if(u.key==INT_MAX) continue;
for(edge e: adjList[u.data]){
relax(u.data,e.to,e.w);
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i=0;i<M;i++){
int u=R[i][0];
int v=R[i][1];
edge e={v,L[i]};
adjList[u].push_back(e);
e.to=u;
adjList[v].push_back(e);
}
dijkstra(N,K,P);
int secondBest=second[0];
return secondBest;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |