#include "crocodile.h"
#include <iostream>
using namespace std;
long long int fin[100005],t[20000005],c[100005],road[5000005][3],map[100005],mi[100005][2],tag[100005];
int dfs(int x){
//cout<<x<<endl;
int q=map[x];
tag[x]=1;
while(q!=-1)
{
//cout<<c[road[q][0]]<<" "<<tag[road[q][0]]<<endl;
if(c[road[q][0]]>=2 && tag[road[q][0]]==0)
{
if(mi[road[q][0]][1]==9999999999)dfs(road[q][0]);
if(mi[road[q][0]][1]+road[q][2]<mi[x][0])
{
mi[x][1]=mi[x][0];
mi[x][0]=mi[road[q][0]][1]+road[q][2];
}
else if(mi[road[q][0]][1]+road[q][2]<mi[x][1])
{
mi[x][1]=mi[road[q][0]][1]+road[q][2];
}
}
q=road[q][1];
}
tag[x]=0;
return 0;
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
for(int i=0;i<n;i++)map[i]=-1;
for(int i=0;i<m;i++)
{
road[i*2][0]=r[i][0];
road[i*2][1]=map[r[i][1]];
road[i*2][2]=l[i];
map[r[i][1]]=i*2;
road[i*2+1][0]=r[i][1];
road[i*2+1][1]=map[r[i][0]];
road[i*2+1][2]=l[i];
map[r[i][0]]=i*2+1;
}
//for(int i=0;i<n;i++)cout<<map[i]<<" ";
//cout<<endl;
//for(int i=0;i<=(m-1)*2;i++)
// cout<<i<<" "<<road[i][0]<<" "<<road[i][1]<<" "<<road[i][2]<<endl;
for(int i=0;i<n;i++)
{
mi[i][0]=9999999999;
mi[i][1]=9999999999;
}
for(int i=0;i<k;i++)
{
c[p[i]]=2;
mi[p[i]][0]=0;
mi[p[i]][1]=0;
}
int pp=0,qq=k-1;
for(int i=0;i<k;i++)t[i]=p[i];
while(pp<=qq)
{
if(c[t[pp]]>=2&& fin[t[pp]]==0)
{
//cout<<t[pp]<<" ";
int q=map[t[pp]];
while(q!=-1)
{
//cout<<q<<" "<<road[q][0]<<" ";
//system("pause");
if(fin[road[q][0]]==0)
{
qq++;
c[road[q][0]]++;
t[qq]=road[q][0];
}
q=road[q][1];
}
//cout<<endl;
fin[t[pp]]=1;
}
pp++;
}
for(int i=0;i<k;i++)t[i]=p[i];
pp=0;
qq=k-1;
for(int i=0;i<n;i++)fin[i]=0;
while(pp<=qq)
{
while((fin[t[pp]]==1 || mi[t[pp]][1]==9999999999) && pp<=qq)pp++;
if(pp>qq)break;
int q=map[t[pp]];
//cout<<t[pp]<<" "<<mi[t[pp]][1]<<" ";
while(q!=-1)
{
//cout<<road[q][0]<<" "<<mi[road[q][0]][0]<<" "<<mi[road[q][0]][1]<<" ";
//if(road[q][0]==0)system("pause");
if(c[road[q][0]]>=2)
{
qq++;
t[qq]=road[q][0];
if(mi[t[pp]][1]+road[q][2]<mi[road[q][0]][0])
{
fin[road[q][0]]=0;
mi[road[q][0]][1]=mi[road[q][0]][0];
mi[road[q][0]][0]=mi[t[pp]][1]+road[q][2];
}
else if(mi[t[pp]][1]+road[q][2]<mi[road[q][0]][1])
{
fin[road[q][0]]=0;
mi[road[q][0]][1]=mi[t[pp]][1]+road[q][2];
}
}
q=road[q][1];
}
//cout<<endl;
//cout<<mi[0][0]<<" "<<mi[0][1]<<endl;
fin[t[pp]]=1;
pp++;
}
//cout<<mi[0][0]<<" "<<mi[0][1]<<endl;
//for(int i=0;i<n;i++)cout<<c[i]<<" ";
//cout<<endl;
//dfs(0);
//for(int i=0;i<n;i++)cout<<mi[i][0]<<" "<<mi[i][1]<<endl;;
//cout<<endl;
return mi[0][1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
