| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 672540 | 2022-12-16T14:28:13 Z | mmk | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KB |
#include "crocodile.h"
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define long long ll;
using namespace std;
const int MAXN = 1e5+10;
ll Dist1[MAXN], Dist2[MAXN];
int marc[MAXN];
vector<int> grafo[MAXN];
vector<int> weight[MAXN];
ll travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
for(int i = 0; i < n; i++)
{
int a = r[i][0];
int b = r[i][1];
grafo[a].push_back(b);
grafo[b].push_back(a);
weight[a].push_back(l[i]);
weight[b].push_back(l[i]);
}
set<pair<ll,int>> s;
for(int i = 0; i < n; i++)
{
Dist1[i] = INF;
Dist2[i] = INF;
}
for(int i = 0; i < k; i++)
{
Dist1[p[i]] = 0;
Dist2[p[i]] = 0;
s.insert({0,p[i]});
}
while(!s.empty())
{
int cur = s.begin()->second;
if(marc[cur] == 1) continue;
marc[cur] = 1;
for(int i = 0; i < grafo[cur].size(); i++)
{
int viz grafo[cur][i];
ll p = weight[cur][i];
if(Dist2[cur] + p < Dist1[viz])
{
Dist2[viz] = Dist1[viz];
Dist1[viz] = Dist2[cur] + p;
s.insert({Dist2[viz],viz});
}
else if(Dist2[cur] + p < Dist2[viz])
{
Dist2[viz] = Dist2[cur] + p;
s.insert({Dist2[viz],viz});
}
}
}
return Dist2[0];
}