| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1288466 | nemkho | 악어의 지하 도시 (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pr pair <ll, int>
using namespace std;
const int N = 2e5 + 5;
int n, m, r, val[N];
vector <pr> a[N];
ll d[N][2];
//void inp()
//{
// cin >> n >> m >> r;
// for (int i = 1; i <= m; i++)
// {
// int x, y;
// ll w;
// cin >> x >> y >> w;
// x++;
// y++;
// a[x].push_back({w, y});
// a[y].push_back({w, x});
// }
// for (int i = 1; i <= r; i++)
// {
// cin >> val[i];
// val[i]++;
// }
//}
void dijkstra ()
{
priority_queue <pr, vector <pr>, greater <pr>> q;
memset(d, 0x3f, sizeof(d));
for (int i = 1; i <= r; i++)
{
q.push({0, val[i]});
d[val[i]][0] = d[val[i]][1] = 0;
}
while (!q.empty())
{
int u = q.top().se;
ll k = q.top().fi;
q.pop();
if (k > d[u][1])
continue;
for (pr i : a[u])
{
int v = i.se;
ll sum = d[u][1] + i.fi;
if (sum < d[v][0])
{
d[v][1] = d[v][0];
d[v][0] = sum;
q.push({d[v][0], v});
q.push({d[v][1], v});
}
else if (sum < d[v][1])
{
d[v][1] = sum;
q.push({d[v][1], v});
}
}
}
}
//void solve()
//{
// dijkstra();
// cout << d[1][1];
//}
ll travel_plan (int n, int m, int r[][], ll l[], int k, int p[])
{
for (int i = 0; i < m; i++)
{
a[r[i][0]+1].push_back({l[i], r[i][1]+1});
a[r[i][1]+1].push_back({l[i], r[i][0]+1});
}
for (int i = 0; i < k; i++)
val[i+1] = p[i] + 1;
dijkstra();
return d[1][1];
}
//int main()
//{
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("TEST.INP","r",stdin);
// freopen("TEST.OUT","w",stdout);
// inp();
// solve();
//}