#include "crocodile.h"
#include <iostream>
#include <cstdlib>
#define maxn 100005
#define maxm 1000005
using namespace std;
long long map[4*maxm][3],o;
long long a[4*maxm][3];
long long way[maxn];
long long sort[maxm][2];
long long heap[4*maxm][2],ho=0;
long long d[maxn];
void down(long long point,long long value, long long x)
{
ho++;
x++;
heap[x][0]=point;
heap[x][1]=value;
while(heap[x][1]<heap[x/2][1]&&x>1)
{
swap(heap[x][0],heap[x/2][0]);
swap(heap[x][1],heap[x/2][1]);
x=x/2;
}
}
void push(long long point)
{
long long p=point;
while(a[p][0]!=-1)
{
p=a[p][0];
if(a[p][0]!=-1)down(a[p][1],d[point]+a[p][2],ho);
}
}
void pop()
{
long long temp=heap[1][0],t=0;
if(d[heap[1][0]]==-1)
{
t=1;
d[heap[1][0]]=heap[1][1];
}
else d[heap[1][0]]=min(d[heap[1][0]],heap[1][1]);
swap(heap[1][0],heap[ho][0]);
swap(heap[1][1],heap[ho][1]);
ho--;
long long x=1;
if(ho>0)
{
while((heap[x][1]>heap[2*x][1]&&2*x<=ho)||(heap[x][1]>heap[2*x+1][1]&&2*x+1<=ho))
{
if((heap[x][1]>heap[2*x][1]&&2*x<=ho)&&(heap[x][1]>heap[2*x+1][1]&&2*x+1<=ho))
{
if(heap[2*x][1]>heap[2*x+1][1]&&2*x<=ho)
{
swap(heap[x][0],heap[2*x][0]);
swap(heap[x][1],heap[2*x][1]);
x=2*x;
}
else if(2*x+1<=ho)
{
swap(heap[x][0],heap[2*x+1][0]);
swap(heap[x][1],heap[2*x+1][1]);
x=2*x+1;
}
}
else if(heap[x][1]>heap[2*x][1]&&2*x<=ho)
{
swap(heap[x][0],heap[2*x][0]);
swap(heap[x][1],heap[2*x][1]);
x=2*x;
}
else if(2*x+1<=ho)
{
swap(heap[x][0],heap[2*x+1][0]);
swap(heap[x][1],heap[2*x+1][1]);
x=2*x+1;
}
}
}
if(t==1&&way[temp]==0)push(temp);
}
int compare(const void *x, const void *y)
{
return ((long long*)x)[1] - ((long long*)y)[1];
}
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
for(long long i=0;i<4*maxm;i++)
{
map[i][0]=-1;
a[i][0]=-1;
heap[i][0]=-1;
heap[i][1]=-1;
}
for(long long i=0;i<maxn;i++)d[i]=-1;
for(long long i=0;i<n;i++)way[i]=0;
for(long long i=0;i<K;i++)way[P[i]]=1;
o=n-1;
for(long long i=0;i<m;i++)
{
o++;
map[o][1]=R[i][1];
map[o][2]=L[i];
map[o][0]=map[R[i][0]][0];
map[R[i][0]][0]=o;
o++;
map[o][1]=R[i][0];
map[o][2]=L[i];
map[o][0]=map[R[i][1]][0];
map[R[i][1]][0]=o;
}
/* for(long long i=0;i<=o;i++)cout<<i<<"\t";cout<<endl;
for(long long i=0;i<=o;i++)cout<<map[i][0]<<"\t";cout<<endl;
for(long long i=0;i<=o;i++)cout<<map[i][1]<<"\t";cout<<endl;
for(long long i=0;i<=o;i++)cout<<map[i][2]<<"\t";cout<<endl;
cout<<"---------------------"<<endl;*/
o=n-1;
for(long long i=0;i<n;i++)
{
long long p=i,lo=1,oo=0;
while(map[p][0]!=-1)
{
p=map[p][0];
oo++;
sort[oo][0]=map[p][1];
sort[oo][1]=map[p][2];
if(way[map[p][1]]==1)
{
swap(sort[oo][0],sort[lo][0]);
swap(sort[oo][1],sort[lo][1]);
lo++;
}
}
qsort(sort+lo,oo-lo+1,sizeof(long long)*2,compare);
if(lo>1)qsort(sort+1,lo-1,sizeof(long long)*2,compare);
/*cout<<i<<","<<lo<<","<<oo<<":"<<endl;
for(long long j=1;j<=oo;j++)cout<<j<<"\t";cout<<endl;
for(long long j=1;j<=oo;j++)cout<<sort[j][0]<<"\t";cout<<endl;
for(long long j=1;j<=oo;j++)cout<<sort[j][1]<<"\t";cout<<endl;
cout<<"------------------------"<<endl;*/
for(long long j=1;j<=oo;j++)
{
o++;
a[o][1]=sort[j][0];
a[o][2]=sort[j][1];
a[o][0]=a[i][0];
a[i][0]=o;
}
}
/* for(long long i=0;i<=o;i++)cout<<i<<"\t";cout<<endl;
for(long long i=0;i<=o;i++)cout<<a[i][0]<<"\t";cout<<endl;
for(long long i=0;i<=o;i++)cout<<a[i][1]<<"\t";cout<<endl;
for(long long i=0;i<=o;i++)cout<<a[i][2]<<"\t";cout<<endl;
cout<<"---------------------"<<endl;*/
d[0]=0;
push(0);
while(ho>0)
{
/* for(long long i=1;i<=ho;i++)cout<<i<<"\t";cout<<endl;
for(long long i=1;i<=ho;i++)cout<<heap[i][0]<<"\t";cout<<endl;
for(long long i=1;i<=ho;i++)cout<<heap[i][1]<<"\t";cout<<endl;*/
pop();
/* for(long long i=1;i<=ho;i++)cout<<i<<"\t";cout<<endl;
for(long long i=1;i<=ho;i++)cout<<heap[i][0]<<"\t";cout<<endl;
for(long long i=1;i<=ho;i++)cout<<heap[i][1]<<"\t";cout<<endl;*/
}
long long ans=-1;
for(long long i=0;i<K;i++)if((d[P[i]]<ans||ans==-1)&&d[P[i]]!=-1)ans=d[P[i]];
// for(long long i=0;i<n;i++)cout<<d[i]<<"\t";cout<<endl;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
251668 KB |
Output is correct |
| 2 |
Incorrect |
222 ms |
251640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
251668 KB |
Output is correct |
| 2 |
Incorrect |
222 ms |
251640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
251668 KB |
Output is correct |
| 2 |
Incorrect |
222 ms |
251640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
