Submission #1218990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218990		niwrad	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	1 ms	580 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
long long inf = 1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  int n = M;
  vector<vector<pair<int, long long>>> graph(N);
  vector<int> vis(n);
  vector<pair<long long, long long>> dis(n, {inf, inf});
  for (int i = 0; i < M; i++) {
    graph[R[i][0]].push_back({R[i][1], L[i]});
    graph[R[i][1]].push_back({R[i][0], L[i]});
  }
  priority_queue<pair<long long, int>> pq;
  for (int i = 0; i < K; i++) {
    vis[P[i]] = 1;
    for (auto adj : graph[P[i]]) {
      if (!vis[adj.first]) {
        long long comp = adj.second;
        if (comp < dis[adj.first].first) {
          long long im = comp;
          comp = dis[adj.first].first;
          dis[adj.first].first = im;
        }
        if (comp < dis[adj.first].second) {
          dis[adj.first].second = comp;
          pq.push({-dis[adj.first].second, adj.first});
        }
      }
    }
  }
  while (pq.size() > 0) {
    auto t = pq.top();
    pq.pop();
    if (vis[t.second]) {
      continue;
    }
    vis[t.second] = 1; 
    long long d = -t.first;
    for (auto adj : graph[t.second]) {
      if (!vis[adj.first]) {
        long long comp = adj.second + d;
        if (comp < dis[adj.first].first) {
          long long im = comp;
          comp = dis[adj.first].first;
          dis[adj.first].first = im;
        }
        if (comp < dis[adj.first].second) {
          dis[adj.first].second = comp;
          pq.push({-dis[adj.first].second, adj.first});
        }
      }
    }
  }
  return dis[0].second;
}

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