제출 #763831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763831		gg123_pe	사이버랜드 (APIO23_cyberland)	C++17	44 / 100	38 ms	10144 KiB

cyberland

#include <bits/stdc++.h> 
#include "cyberland.h"

using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
typedef pair <double, int> ii; 

const int N = 1e5 + 5; 
const double inf = 2e15; 

int n; 
double d[N]; 
bool vis[N]; 
vector <pair<int, double>> adj[N], adj_H; 
vector <int> ARR; 

void check(int u){
    vis[u] = 1; 
    for(auto p: adj[u]){
        int v = p.first; 
        if(!vis[v]) check(v); 
    }
}
void clear(){
    adj_H.clear(); ARR.clear();  
    f(i,0,n) adj[i].clear(), vis[i] = 0; 
}
void dij(){
    priority_queue <ii, vector <ii>, greater <ii>> q; 
    f(i,0,n) {
        d[i] = inf; 
        if((ARR[i] == 0 or i == 0) and vis[i]){
            d[i] = 0; 
            q.push({0, i}); 
        }
    }

    while(!q.empty()){
        auto pa = q.top(); q.pop(); 
        double d_u = pa.first; int u = pa.second; 

        if(d[u] != d_u) continue; 
        for(auto p: adj[u]){
            int v = p.first; double w = p.second; 
            if(d[v] > d[u] + w){
                d[v] = d[u] + w; 
                q.push({d[v], v}); 
            }
        }
    }
}
double solve(int Ni, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    n = Ni; 
    ARR = arr; 

    f(i,0,M){
        if(x[i] == H or y[i] == H){
            adj_H.push_back({x[i] + y[i] - H, c[i]}); 
        }
        else {
            adj[x[i]].push_back({y[i], c[i]}); 
            adj[y[i]].push_back({x[i], c[i]}); 
        }
    }
    check(0); 
    dij(); 
    
    double ans = inf; 
    for(auto p: adj_H) {
        int v = p.first; double w = p.second; 
        if(vis[v]) ans = min(ans, d[v] + w); 
    }
    clear(); 
    return (ans == inf) ? -1 : ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3