제출 #883310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883310		vjudge1	공장들 (JOI14_factories)	C++17	15 / 100	4224 ms	56148 KiB

factories

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

typedef long long ll;
const ll INF = 1'000'000'000'000'000'000;

const int N = 5000;

int n, q;
ll dis[N + 10];
vector<pair<int, ll>> adj[N + 10];
vector<int> vec1, vec2;

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

void dij() {
    fill(dis + 0, dis + n + 1, INF);
    set<pair<ll, int>> st;
    for (auto t: vec1) {
        dis[t] = 0;
        st.insert({0, t});
    }
    while (!st.empty()) {
        int u = st.begin() -> second;
        st.erase(st.begin());
        for (auto [v, w]: adj[u])
            if (dis[u] + w < dis[v]) {
                st.erase({dis[v], v});
                dis[v] = dis[u] + w;
                st.insert({dis[v], v});
            }
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) 
        vec1.push_back(X[i]);
    for (int i = 0; i < T; i++)
        vec2.push_back(Y[i]);
    dij();
    ll mn = INF;
    for (auto t: vec2)
        mn = min(mn, dis[t]);
    vec1.clear();
    vec2.clear();
    return mn;
}

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