# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
208608 | Kenzo_1114 | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include"crocodile.h"
using namespace std;
const int MAXN = 100010;
const int MAXM = 1000010;
const long long INF = 1e18 + 7;
int N, M, R[MAXM][2], K, P[MAXN];
long long L[MAXM];
long long dist[MAXN], dist2[MAXN];
vector<int> graf[MAXN];
vector<long long> cost[MAXN];
void DIK(int n)
{
set<pair<pair<long long, long long>, int> > s;
for(int i = 0; i < n; i++)
s.insert({{dist[i], dist2[i]}, i});
while(!s.empty())
{
int cur = s.begin()->second;
s.erase(s.begin());
for(int i = 0; i < graf[cur].size(); i++)
{
int adj = graf[cur][i];
long long c = cost[cur][i];
long long DIST = dist2[cur];
if(dist[adj] > DIST + c)
{
s.erase({{dist[adj], dist2[adj]}, adj});
dist2[adj] = dist[adj], dist[adj] = DIST + c;
s.insert({{dist[adj], dist2[adj]}, adj});
}
else if(dist2[adj] > DIST + c)
{
s.erase({{dist[adj], dist2[adj]}, adj});
dist2[adj] = DIST + c;
s.insert({{dist[adj], dist2[adj]}, adj});
}
}
}
}
long long travel_plan(int n, int m, int r[][2], long long l[], int k, int p[])
{
for(int i = 0; i < M; i++)
{
int a = r[i][0];
int b = r[i][1];
graf[a].push_back(b);
graf[b].push_back(a);
cost[a].push_back(l[i]);
cost[b].push_back(l[i]);
}
for(int i = 0; i < k; i++)
dist[i] = dist2[i] = INF;
for(int i = 0; i < k; i++)
dist[p[i]] = dist2[p[i]] = 0;
DIK(n);
return dist2[0];
}
/*
int main ()
{
scanf("%d %d", &N, &M);
for(int i = 0; i < M; i++)
scanf("%d %d", &R[i][0], &R[i][1]);
for(int i = 0; i < M; i++) scanf("%lld", &L[i]);
scanf("%d", &K);
for(int i = 0; i < K; i++) scanf("%d", &P[i]);
printf("%lld\n", travel_plan(N, M, R, L, K, P));
}
*/