Submission #735594

#	Time	Username	Problem	Language	Result	Execution time	Memory
735594		Jeff12345121	Factories (JOI14_factories)	C++14	0 / 100	8096 ms	47012 KiB

factories

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

typedef long long ll;
vector<vector<pair<int,int>>> g;
int n;

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

const ll inf = (1LL << 60);
ll get_dis(int u, int v) {
    vector<ll> dis(n + 1,-1);
    function<void(int)> dfs = [&](int node) {
        for (auto k : g[node]) {
            if (dis[k.first] == -1) {
                dis[k.first] = dis[node] + k.second;
                dfs(k.first);
            }
        }  
    };

    dis[u] = 0;
    dfs(u);
    return dis[v];
}
long long Query(int S, int X[], int T, int Y[]) {
    ll sol = inf;
    for (int i = 1; i <= S; i++) {
        for (int j = 1; j <= T; j++) {
            sol = min(sol , get_dis(X[i - 1] , Y[j - 1]));
        }
    }
    return sol;
}

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