Submission #1201978

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

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i = a; i <= b; ++i)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define pii pair<int,int>

const int MAXN = 1e5 + 10;
const int INF = 1e9 + 5;
vector<pii> g[MAXN];
int dist[MAXN], mk[MAXN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  rep(i,0,M-1) {
    int u = R[i][0], v= R[i][1], w= L[i];
    g[u].pb({v,w});
    g[v].pb({u,w});
  }
  priority_queue<pii,vector<pii>,greater<pii>> pq;
  rep(i,0,K-1) pq.push({0,P[i]});
  rep(i,0,N) dist[i] = INF;

  while (!pq.empty()) {
    pii tp = pq.top();
    int cw = tp.first,u = tp.second;
    pq.pop();
    if (dist[u] < INF) continue;
    dist[u] = cw;
    for (const auto &e : g[u]) {
      int v = e.first, w = e.second;
      if (dist[v] > cw + w) {
        pq.push({cw+w,v});
      }
    }
  }
  
  int ans = 0, cur = 0;
  while (dist[cur] != 0) {
    vector<pair<int,pii>> haha;
    mk[cur] = 1;
    for(const auto &e : g[cur]) {
      int v = e.first, w = e.second;
      if (mk[v]) continue;
      haha.pb({dist[v]+w,{v,w}});
    }
    sort(all(haha));
    cur = haha[1].second.first;
    ans += haha[1].second.second;

  }

  return ans;
}

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