#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define X first
#define Y second
int n,m,k,p[100005],y,cost,d[100005][2],u,vis[100005],deg[100005];
vector<pair<int,int> > g[100005];
priority_queue<pair<int,int> > pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n=N;
for(int i=1;i<=n;i++)
{
d[i][0]=1e9;
d[i][1]=1e9;
}
m=M;
for(int i=0;i<m;i++)
{
g[R[i][0]+1].pb({R[i][1]+1,L[i]});
g[R[i][1]+1].pb({R[i][0]+1,L[i]});
}
k=K;
for(int i=0;i<k;i++)
{
p[i+1]=P[i]+1;
}
for(int i=1;i<=k;i++)
{
d[p[i]][0]=0;
d[p[i]][1]=0;
pq.push({0,p[i]});
}
/*while(!pq.empty())
{
printf("%d %d\n",pq.top().X,pq.top().Y);
pq.pop();
}*/
while(!pq.empty())
{
u=pq.top().Y;
//printf("%d %d %d\n",u,d[u][0],d[u][1]);
if(vis[u]==1)continue;
vis[u]=0;
pq.pop();
for(auto [y,cost]:g[u])
{
// if(d[y][0]==2e9&&d[y][1]==2e9)
// {
// d[y][0]=d[u][1]+cost;
// d[y][1]=d[u][1]+cost;
// pq.push({-d[y][1],y});
// continue;
// }
if(d[u][1]+cost<=d[y][0])
{
d[y][1]=d[y][0];
d[y][0]=d[u][1]+cost;
}else if(d[u][1]+cost<d[y][1])
{
d[y][1]=d[u][1]+cost;
}
if(++deg[y]>=2&&vis[y]==0)
{
pq.push({-d[y][1],y});
}
}
}
return d[1][1];
}
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:49:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
49 | for(auto [y,cost]:g[u])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2094 ms |
134196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2094 ms |
134196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2094 ms |
134196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
