Submission #978943

#	Time	Username	Problem	Language	Result	Execution time	Memory
978943		Panda50O	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	1 ms	4444 KiB

crocodile

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

#define MAX_N 50005
#define MAX_M 1000005
#define pii pair<int,int>

const int INF = 2e9+5;
vector<pair<int,int>> adj[MAX_N];
// int N, M, R[MAX_M][2], L[MAX_M], K, P[MAX_N];
int mn_target[MAX_N][2], dist[MAX_N];
bool target[MAX_N], vis[MAX_N];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(int i = 0; i < N; ++i) {
    mn_target[i][0] = INF;
    mn_target[i][1] = INF;
    dist[i] = INF;
  }
  for(int i = 0; i < M; ++i) {
    int a = R[i][0], b = R[i][1], c = L[i];
    adj[a].emplace_back(b, c);
    adj[a].emplace_back(b, c);
  }
  for(int i = 0; i < K; ++i) {
    target[P[i]] = true;
  }

  for(int i = 0; i < M; ++i) {
    int a = R[i][0], b = R[i][1], c = L[i];
    if((target[a] && target[b]) || (!target[a] && !target[b])) continue;
    if(target[a]) swap(a, b);
    if(c <= mn_target[a][0]) {
      mn_target[a][1] = mn_target[a][0];
      mn_target[a][0] = c;
    } else if (c < mn_target[a][1]) {
      mn_target[a][1] = c;
    }
  }

  pq.emplace(0, 0);
  dist[0] = 0;
  while(!pq.empty()) {
    // auto [d, u] = pq.top();
    int u = pq.top().second;
    pq.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(auto p : adj[u]) {
      int v = p.first;
      int w = p.second;
      if(target[v]) continue;
      if(!vis[v] && dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        pq.emplace(dist[v], v);
      }
    }
  }

  int ans = INF;
  for(int i = 0; i < N; ++i) {
    if(target[i]) continue;
    ans = min(ans, dist[i] + mn_target[i][1]);
  }
  return ans;
}


// int main() {
//   ios_base::sync_with_stdio(0); cin.tie(0);
//   int ans;
//   cin >> N >> M >> K;
//   for(int i = 0; i < M; ++i)
//     cin >> R[i][0] >> R[i][1] >> L[i];  
//   for(int i = 0; i < K; ++i)
//     cin >> P[i];

//   ans = travel_plan(N,M,R,L,K,P);
//   cout << ans;
// }

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