제출 #1140762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140762		0x34c	악어의 지하 도시 (IOI11_crocodile)	C++20	0 / 100	0 ms	320 KiB

crocodile

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define plii pair<ll, pii>
#define pli pair<ll, int>
#include "crocodile.h"

using namespace std;

const ll INF = 1e15;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  vector<vector<pii>> graph(N);
  vector<bool> exit(N, false);
  int end = P[0];

  for (int k = 0; k < K; k++)
    exit[P[k]] = true;

  for (int i = 0; i < M; i++)
  {
    if (exit[R[i][0]] && exit[R[i][1]])
      continue;

    if (exit[R[i][0]])
    {
      graph[end].push_back({R[i][1], L[i]});
      graph[R[i][1]].push_back({end, L[i]});
    }
    else if (exit[R[i][1]])
    {
      graph[end].push_back({R[i][0], L[i]});
      graph[R[i][0]].push_back({end, L[i]});
    }
    else
    {
      graph[R[i][0]].push_back({R[i][1], L[i]});
      graph[R[i][1]].push_back({R[i][0], L[i]});
    }
  }

  vector<vector<ll>> dist(N, vector<ll>(2, INF));
  dist[end][0] = dist[end][1] = 0;

  priority_queue<pli, vector<pli>, greater<pli>> q;
  q.push({0, end});

  while (!q.empty())
  {
    ll w;
    int v;
    tie(v, w) = q.top();
    q.pop();

    if (dist[v][1] < w)
      continue;

    for (pli e : graph[v])
    {
      ll wei;
      int u;
      tie(u, wei) = e;

      if (dist[u][1] <= w + wei)
        continue;

      if (dist[u][0] > w + wei)
      {
        if (dist[u][0] < INF)
          q.push({dist[u][0], u});

        dist[u][1] = dist[u][0];
        dist[u][0] = w + wei;
      }
      else if (dist[u][1] > w + wei)
      {
        dist[u][1] = w + wei;
        q.push({w + wei, u});
      }
    }
  }

  return dist[0][1];
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11