| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1228039 | vako_p | 서열 (APIO23_sequence) | C++20 | 0 ms | 0 KiB |
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define sd second
void dfs(int H, int at, vector<vector<pair<int,int>>>& v, vector<bool>& vis, vector<int>& arr, vector<int>& vv){
if(vis[at]) return;
// cout <<" ---> " << at << endl;
vis[at] = true;
if(at == H) return;
if(!arr[at]) vv.pb(at);
for(auto it1 : v[at]){
int it = it1.ff;
dfs(H, it, v, vis, arr, vv);
}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
int n = N,m = M,k = K;
vector<vector<pair<int,int>>> v(n);
k = min(k, 30);
for(int i = 0; i < m; i++){
v[x[i]].pb({y[i], c[i]});
v[y[i]].pb({x[i], c[i]});
}
priority_queue<pair<int,pair<double,int>>, vector<pair<int,pair<double,int>>>, greater<pair<int,pair<double,int>>>> q;
vector<vector<double>> dis(35, vector<double>(n, 1e18));
vector<bool> vis1(n, false);
vector<vector<bool>> vis(35, vector<bool>(n, false));
vector<int> vv;
dfs(H, 0, v, vis1, arr, vv);
if(!vis1[H]) return -1;
for(int i = 0; i <= k; i++) dis[i][0] = 0;
q.push({-k, {0, 0}});
for(auto it : vv){
for(int i = 0; i <= k; i++) dis[i][it] = 0;
q.push({-k, {0, it}});
}
while(!q.empty()){
int curr = -q.top().ff,at = q.top().sd.sd;
q.pop();
if(vis[curr][at] or at == H) continue;
vis[curr][at] = true;
double val = dis[curr][at];
for(auto it1 : v[at]){
int it = it1.ff;
if(vis[curr][it]) continue;
if(dis[curr][it] > val + it1.sd){
dis[curr][it] = val + it1.sd;
q.push({-curr, {dis[curr][it], it}});
}
}
if(arr[at] == 2 and curr){
curr--;
val /= 2;
for(auto it1 : v[at]){
int it = it1.ff;
if(vis[curr][it]) continue;
if(dis[curr][it] > val + it1.sd){
dis[curr][it] = val + it1.sd;
q.push({-curr, {dis[curr][it], it}});
}
}
}
}
double ans = 1e18;
for(int i = 0; i <= k; i++) ans = min(ans, dis[i][H]);
return ans;
}