| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1137341 | Iwanttobreakfree | 악어의 지하 도시 (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
// Multi-Dijkstra
vector<vector<long long>> Dijkstra(int K, int P[], vector<vector<pair<int,int>>>& lista) {
int n = lista.size();
priority_queue<pair<pair<long long,int>, bool>> pq; // log N
vector<vector<long long>> dist(n, vector<long long> (2, 1e18)); // nos guardamos las rutas alternativas
// dist[v][0] nos guardamos la segunda distancia mas corta a una de las salidas
// dist[v][1] nos guardamos la primera distancia mas corta a una de las salidas
vector<bool> seen(n);
for (int i = 0; i < K; ++i) {
dist[P[i]][1] = 0;
dist[P[i]][0] = 0;
pq.push({{dist[P[i]][0], P[i]}, 0});
}
while (!pq.empty()) {
int nodoActual = pq.top().first.second;
long long distActual = -pq.top().first.first;
bool masCorta = pq.top().second;
pq.pop();
if (dist[nodoActual][masCorta] < distActual || seen[nodoActual]) continue;
seen[nodoActual] = true;
for (auto vecino: lista[nodoActual]) {
int nextNodo = vecino.first, w = vecino.second;
// Actualizar distancia mas corta
if (dist[nextNodo][true] > dist[nodoActual][false] + w) { // Hemos encontrado una ruta alternativa que mejora la anterior
dist[nextNodo][false] = dist[nodoActual][true];
dist[nextNodo][true] = dist[nodoActual][false] + w;
if (dist[nextNodo][true] != dist[nextNodo][false]) pq.push({{-dist[nextNodo][false], nextNodo}, false})
} // Solo se actualiza la segunda
else if (dist[nextNodo][false] > dist[nodoActual][false] + w) { // Hemos encontrado una ruta alternativa que mejora la anterior
dist[nextNodo][false] = dist[nodoActual][false] + w;
pq.push({{-dist[nextNodo][false], nextNodo}, false});
}
}
}
return dist;
}
/*
Cocodrilo
Primera prioridad: Conseguir que no salgamos del laberinto
Segunda prioridad: Estemos el máximo de tiempo posible
*/
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vector<pair<int,int>>> lista(N, vector<pair<int,int>>());
for (int i = 0; i < M; ++i) {
lista[R[i][0]].push_back({R[i][1], L[i]});
lista[R[i][1]].push_back({R[i][0], L[i]});
}
vector<bool> esSalida(N);
for (int i = 0; i < K; ++i) esSalida[P[i]] = true;
vector<vector<long long>> dist = Dijkstra(K, P, lista);
return dist[0][0];
}