| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1217143 | LmaoLmao | 악어의 지하 도시 (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "crocodile.h"
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>;
const int N = 1e6+5;
const int INF = 1e9;
const int mod = 1e9+7;
vector<ii> adj[100005];
ii edge[100005];
int d[100005][2];
signed travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int n=N,m=M,k=K;
for(int i=0;i<m;i++) {
int x=L[i];
int u=R[i][0],v=R[i][1];
adj[u].push_back({v,x});
adj[v].push_back({u,x});
//cout << u << ' ' << v << ' ' << x << endl;
}
priority_queue<aa,vector<aa>,greater<aa>> q;
for(int i=0;i<n;i++) {
d[i][0]=d[i][1]=1e18;
}
for(int i=0;i<k;i++) {
int x=P[i];
d[x][0]=0;
d[x][1]=0;
q.push({0,x,0});
}
while(!q.empty()) {
aa u=q.top();
q.pop();
if(u[0]>d[u[1]][u[2]] ) continue;
//cout << u[0] << ' ' << u[1] << ' ' << u[2] << endl;
for(ii v:adj[u[1]]) {
if(d[v.fi][1]>v.se+u[0]) {
d[v.fi][1]=v.se+u[0];
//cout << d[v.fi][0] << ' ' << d[v.fi][1] << ' '<< v.se << ' ' << v.fi << endl;
if(d[v.fi][0]>d[v.fi][1]) {
swap(d[v.fi][0],d[v.fi][1]);
}
//cout << d[v.fi][0] << ' ' << d[v.fi][1] << ' '<< v.se << ' ' << v.fi << endl;
q.push({d[v.fi][1],v.fi,1});
}
}
//break;
}
return d[0][1];
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░ ░██████╗██╗██╗░░░██╗ ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░ ██╔════╝██║██║░░░██║ ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░ ╚█████╗░██║██║░░░██║ ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗ ░╚═══██╗██║██║░░░██║ ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝ ██████╔╝██║╚██████╔╝ ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░ ╚═════╝░╚═╝░╚═════╝░ ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/