| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1337292 | kitijak | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
#define pii pair<long long, long long>
#define pb push_back
#define fi first
#define se second
using namespace std;
vector<pii>graph[500005];
ll n, att[500005];
void Init(int N, int A[], int B[], int D[]){
n=N;
for(int i=0; i<n; i++){
graph[A[i]].pb({D[i], B[i]});
graph[B[i]].pb({D[i], A[i]});
}
}
long long Query(int S, int X[], int T, int Y[]){
ll mn=INT_MAX, atb;
atb=INT_MAX;
fill(att, att+n, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>>pq;
for(int i=0; i<S; i++){
pq.push({0, X[i]});
}
while(!pq.empty()){
ll v=pq.top().se, t=pq.top().fi;
pq.pop();
if(att[v]<=t)
continue;
att[v]=t;
for(auto x : graph[v]){
pq.push({t+x.fi, x.se});
}
}
for(int i=0; i<T; i++)
atb=min(atb, att[Y[i]]);
mn=min(mn, atb);
return mn;
}
