Submission #306142

#	Time	Username	Problem	Language	Result	Execution time	Memory
306142		quocnguyen1012	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	771 ms	47852 KiB

crocodile

#ifndef LOCAL
#include "crocodile.h"
#endif // LOCAL

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;
const ll inf = 1e18;

int N, M, K;
vector<ii> adj[maxn];
ll dist[maxn][2];

int travel_plan(int _N, int _M, int R[][2], int L[], int _K, int P[])
{
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  N = _N, M = _M, K = _K;
  for(int i = 0; i < M; ++i){
    adj[R[i][0]].eb(R[i][1], L[i]);
    adj[R[i][1]].eb(R[i][0], L[i]);
    ///cerr << R[i][0] << ' ' << R[i][1] << ' ' << L[i] << '\n';
  }
  fill_n(&dist[0][0], maxn * 2, inf);
  for(int i = 0; i < K; ++i){
    pq.push(mp(0, P[i]));
    dist[P[i]][0] = dist[P[i]][1] = 0;
  }
  while(pq.size()){
    int now; int u;
    tie(now, u) = pq.top(); pq.pop();
    if(now > dist[u][1]) continue;
    for(auto v : adj[u]){
      ll d = dist[u][1] + v.se;
      if(dist[v.fi][0] > d){
        swap(dist[v.fi][0], dist[v.fi][1]);
        dist[v.fi][0] = d;
        if(dist[v.fi][1] != inf)
          pq.push(mp(dist[v.fi][1], v.fi));
      }
      else if(dist[v.fi][1] > d){
        dist[v.fi][1] = d;
        pq.push(mp(d, v.fi));
      }
    }
    ///cerr << '\n';
  }
  return dist[0][1];
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int _N, _M, _K;
  cin >> _N >> _M >> _K;
  int L[_M], R[_M][2], P[_K];
  for(int i = 0; i < _M; ++i){
    cin >> R[i][0] >> R[i][1];
  }
  for(int i = 0; i < _M; ++i)
    cin >> L[i];
  for(int i = 0; i < _K; ++i)
  cin >> P[i];
  cout << travel_plan(_N, _M, R, L, _K, P);
}
#endif // LOCAL

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