제출 #62004

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

factories

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

int n;
ll dist[5001];
vector <pair <int, ll> > v[5001];

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0 ; i < N ; i++){
        v[A[i]].push_back(make_pair(B[i], D[i]));
        v[B[i]].push_back(make_pair(A[i], D[i]));
    }
}
long long Query(int S, int X[], int T, int Y[]) {
    set <pair <ll, int> > ready;
    for(int i = 0 ; i < n ; i++)
        dist[i] = 1e18;
    for(int i = 0 ; i < S ; i++){
        dist[X[i]] = 0;
        ready.insert(make_pair(0, X[i]));
    }
    while(ready.size()){
        auto cur = *ready.begin();
        ready.erase(ready.begin());
        for(auto &i : v[cur.second]){
            if(i.second + cur.first < dist[i.first]){
                dist[i.first] = i.second + cur.first;
                ready.insert(make_pair(dist[i.first], i.first));
            }
        }
    }
    ll ret = 1e18;
    for(int i = 0 ; i < T ; i++)
        ret = min(ret, dist[Y[i]]);
    return ret;
}

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