#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int data;
ll key;
};
node A[100005];
int heapSize=0;
int leftNode(int i)
{
return i*2;
}
int rightNode(int i)
{
return i*2+1;
}
int parent(int i)
{
return i/2;
}
void minHeapify(int i)
{
int L=leftNode(i);
int R=rightNode(i);
int best;
if(L<=heapSize && A[L].key<A[i].key)
best=L;
else
best=i;
if(R<=heapSize && A[R].key<A[i].key)
best=R;
if(best!=i){
swap(A[i],A[best]);
minHeapify(best);
}
}
void decreaseKey(int i,ll key)
{
if(A[i].key<key) return;
A[i].key=key;
while(i>1 && A[i].key<A[parent(i)].key){
swap(A[i],A[parent(i)]);
i=parent(i);
}
}
void heapInsert(node x)
{
A[++heapSize]=x;
A[heapSize].key=LLONG_MAX;
decreaseKey(heapSize,x.key);
}
node extractMin()
{
node minimum=A[1];
A[1]=A[heapSize--];
minHeapify(1);
return minimum;
}
struct edge
{
int to;
ll w;
};
vector<edge> adjList[100005];
int entrances[100005];
ll d[100005][2]; //0 is primary distance (shortest path),
//1 is secondary distance (second shortest path)
void relax(int u,int v,ll w)
{
entrances[v]++;
if(d[u][1]+w<d[v][0]){
d[v][1]=d[v][0];
d[v][0]=d[u][1]+w;
if(entrances[v]==adjList[v].size()-1 && v!=0){
node x={v,d[v][1]};
heapInsert(x);
}
}
else if(d[u][1]+w<d[v][1]){
d[v][1]=d[u][1]+w;
if(entrances[v]==adjList[v].size()-1 && v!=0){
node x={v,d[v][1]};
heapInsert(x);
}
}
}
int dijkstra(int n,int k,int p[])
{
for(int i=0;i<n;i++){
d[i][0]=d[i][1]=LLONG_MAX/2;
}
for(int i=0;i<k;i++){
int u=p[i];
d[u][0]=d[u][1]=0;
node x={u,0};
heapInsert(x);
}
while(heapSize){
node x=extractMin();
int u=x.data;
for(edge e: adjList[u]){
int v=e.to;
relax(u,v,e.w);
}
}
return d[0][1]; //Secondary distance of node 0 (second best)
}
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);
}
return dijkstra(N,K,P);
}
Compilation message
crocodile.cpp: In function 'void relax(int, int, ll)':
crocodile.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(entrances[v]==adjList[v].size()-1 && v!=0){
~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:84:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(entrances[v]==adjList[v].size()-1 && v!=0){
~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
