#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 ans=-1;
long long d[maxn];
int compare(const void *x, const void *y)
{
return ((long long*)x)[1] - ((long long*)y)[1];
}
void dfs(long long x, long long value)
{
int p=x;
if(way[x]==1)
{
// cout<<value<<endl;
if(ans==-1||value<ans)ans=value;
}
else
{
while(a[p][0]!=-1)
{
p=a[p][0];
if(a[p][0]!=-1)
{
if(d[a[p][1]]==-1||value+a[p][2]<=d[a[p][1]])
{
d[a[p][1]]=value+a[p][2];
dfs(a[p][1],value+a[p][2]);
}
}
}
}
}
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;
}
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;
dfs(0,0);
// for(int i=0;i<n;i++)cout<<d[i]<<"\t";cout<<endl;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
189048 KB |
Output is correct |
| 2 |
Incorrect |
154 ms |
189048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
189048 KB |
Output is correct |
| 2 |
Incorrect |
154 ms |
189048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
189048 KB |
Output is correct |
| 2 |
Incorrect |
154 ms |
189048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
