| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1023112 | clemmy14 | 사이버랜드 (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "cyberland.h"
#define int long long
using namespace std;
int dest;
set<int> posEnd;
vector<bool> visited1;
vector<int> type;
vector<vector<pair<int, int>>> adj;
void dfs(int node) {
if(visited1[node]) return;
visited1[node]=true;
if(node == dest) return;
if(type[node] == 0) posEnd.insert(node);
for(auto child : adj[node]) if(!visited1[child.first]) {
dfs(child.first);
}
}
struct in {
double dis, divPow;
int nbdiv, node;
bool operator< (const in& other) const {
return dis > other.dis;
}
};
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
K = min(K, 70);
dest=H;
type = arr;
visited1 = vector<bool>(N, false);
adj = vector<vector<pair<int, int>>>(N);
for(int i=0; i<M; i++) {
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
posEnd.clear();
posEnd.insert(0);
dfs(0);
if(!visited1[H]) return -1;
vector<vector<bool>> visited(N, vector<bool>(K+1, false));
vector<vector<double>> distance(N, vector<double>(K+1, 1e17)); distance[H][0]=0;
priority_queue<in> q;
in st; st.dis=0; st.divPow=1; st.nbdiv=0; st.node=H;
q.push(st);
while(!q.empty()) {
in cur = q.top(); q.pop();
if(cur.node == H && cur.nbdiv != 0) continue;
if(visited[cur.node][cur.nbdiv]) continue;
if(posEnd.count(cur.node)) return cur.dis;
visited[cur.node][cur.nbdiv]=true;
for(auto [child, childDis] : adj[cur.node]) {
// not dividing by 2
if(distance[cur.node][cur.nbdiv]+childDis/cur.divPow < distance[child][cur.nbdiv]) {
distance[child][cur.nbdiv] = distance[cur.node][cur.nbdiv]+childDis/cur.divPow;
in newV;
newV.dis=distance[child][cur.nbdiv]; newV.node=child;
newV.divPow=cur.divPow; newV.nbdiv=cur.nbdiv;
q.push(newV);
}
// dividing by 2
if(type[child] == 2 && cur.nbdiv+1 <= K && distance[cur.node][cur.nbdiv]+childDis/cur.divPow < distance[child][cur.nbdiv+1]) {
distance[child][cur.nbdiv+1] = distance[cur.node][cur.nbdiv]+childDis/cur.divPow;
in newV;
newV.dis=distance[child][cur.nbdiv+1]; newV.node=child;
newV.divPow=cur.divPow*2; newV.nbdiv=cur.nbdiv+1;
q.push(newV);
}
}
}
return -1;
}