#include "crocodile.h"
#include <iostream>
using namespace std;
long long int e=0,tag[1000005],head[1000005],ans[1000005][2],n,m,map[2000005][3],road[1000005];
int travel_plan(int N, int M, int r[][2], int l[], int k, int p[])
{
n=N;
m=M;
for(int i=0;i<n;i++)road[i]=-1;
for(int i=0;i<=n;i++)
{
int x=r[i][0],y=r[i][1];
map[i*2][0]=y;
map[i*2][1]=road[x];
map[i*2][2]=l[i];
road[x]=i*2;
map[i*2+1][0]=x;
map[i*2+1][1]=road[y];
map[i*2+1][2]=l[i];
road[y]=i*2+1;
}
for(int i=0;i<n;i++)
{
ans[i][0]=999999999999999;
ans[i][1]=999999999999999;
}
e=k;
for(int i=0;i<k;i++)
{
ans[p[i]][0]=0;
ans[p[i]][1]=0;
tag[p[i]]=1;
head[i+1]=p[i];
}
for(int i=0;i<n;i++)
{
int x=head[1];
swap(head[1],head[e]);
e--;
int pe=1;
while(pe*2<=e)
{
if(ans[head[pe]][1]>ans[head[pe*2]][1] || ans[head[pe]][1]>ans[head[pe*2+1]][1])
{
if(ans[head[pe*2+1]][1]<ans[head[pe*2]][1] && pe*2+1<=e)
{
swap(head[pe],head[pe*2+1]);
pe=pe*2+1;
}
else
{
swap(head[pe],head[pe*2]);
pe=pe*2;
}
}
else break;
}
int g=road[x];
//cout<<x<<" "<<ans[x][0]<<" "<<ans[x][1]<<endl;
while(g!=-1)
{
int now=map[g][0];
int tmp=ans[x][1]+map[g][2];
if(tmp<ans[now][0])
{
ans[now][1]=ans[now][0];
ans[now][0]=tmp;
}
else if(tmp<ans[now][1])
{
ans[now][1]=tmp;
}
if(ans[now][1]!=999999999999999 && tag[now]==0)
{
tag[now]=1;
e++;
head[e]=now;
while(e>1)
{
if(ans[head[e]][1]<ans[head[e/2]][1])
{
swap(head[e],head[e/2]);
e/=2;
}
else break;
}
}
g=map[g][1];
}
}
return ans[0][1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
