oj.uz

답안 #345730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345730 2021-01-08T01:48:07 Z casperwang 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 1 ms 364 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pii pair<ll,ll>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 100000;
const ll INF = 1e17;
vector <vector<pii>> path;
vector <pii> dis;
priority_queue <pii, vector<pii>, greater<pii>> nxt;

void init(int N) {
  path.clear();
  path.resize(N);
  dis.clear();
  dis.resize(N);
  for (int i = 0; i < N; i++)
    dis[i].ff = dis[i].ss = INF;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  init(N);
  for (int i = 0; i < M; i++) {
    path[R[i][0]].pb(R[i][1], L[i]);
    path[R[i][1]].pb(R[i][0], L[i]);
  }
  for (int i = 0; i < K; i++) {
    dis[P[i]].ff = dis[P[i]].ss = 0;
    nxt.push(pii(0, P[i]));
  }
  while (nxt.size()) {
    ll now = nxt.top().ss, d = nxt.top().ff;
    nxt.pop();
    for (pii e : path[now]) {
      ll id = e.ff, c = e.ss;
      if (d + c <= dis[id].ff) {
        dis[id].ss = dis[id].ff;
        dis[id].ff = d + c;
        if (dis[id].ss < INF)
          nxt.push(pii(dis[id].ss, id));
      } else if (d + c < dis[id].ss) {
        dis[id].ss = d + c;
        nxt.push(pii(dis[id].ss, id));
      }
    }
  }
  return dis[0].ss;
}

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -