제출 #791289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791289		bane	Factories (JOI14_factories)	C++17	0 / 100	8063 ms	104124 KiB

factories

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

vector<vector<pair<int,int>>>G;

void Init(int N, int A[], int B[], int D[]) {
  G.resize(N+1);
  for (int i = 0; i < N - 1; i++){
    G[A[i]].push_back({B[i], D[i]});
    G[B[i]].push_back({A[i], D[i]});
  }

}

long long Query(int S, int X[], int T, int Y[]) {
  priority_queue<pair<long long, int>>q;
  map<long long, long long>mapa;
  map<int,int>flag;
  for (int i = 0; i < T; i++)flag[Y[i]] = 1;
  for (int i = 0; i < S; i++){
    q.push({0,X[i]});
    mapa[X[i]] = 0;
  }

  while(!q.empty()){
    auto [dist,node] = q.top();
    q.pop();
    dist = -dist;
    if (dist != mapa[node])continue;
    if (flag[node]){
      return dist;
    }
    for(auto edge : G[node]){
      if (!mapa.count(edge.first) || mapa[edge.first] > dist + edge.second){
        mapa[edge.first] = dist + edge.second;
        q.push({-dist-edge.second, edge.first});
      }
    }
  }
  return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67