| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1257428 | Megalosaurus | 사이버랜드 (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
// #include "cyberland.h"
// #include "stub.cpp"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int MXS = 1e5+5;
vector<pair<int,int>>adj[MXS];
int vis[MXS][32];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
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]});
}
vector<vector<double>>d(N, vector<double>(K+1, (double)1e15));
d[0][0] = 0;
for(int i = 0; i < N; i++)
{
if(arr[i] == 0)
{
for(int j = 0; j <= K; j++)
{
d[i][j] = 0;
}
}
}
priority_queue<pair<double,pair<int,int>>>pq;
pq.push({0, {0, 0}});
vis[0][0] = true;
while(pq.size())
{
int node = pq.top().second.first, us = pq.top().second.second;
vis[node][us] = false;
pq.pop();
for(auto [it,ck]:adj[node])
{
if(d[it][us] > d[node][us]+ck)
{
d[it][us] = d[node][us]+ck;
if(!vis[it][us])pq.push({-d[it][us], {it, us}});
vis[it][us] = true;
}
// if(us < K && d[it][us+1] > (d[node][us]+ck)/2.0 && arr[node] == 2)
// {
// d[it][us+1] = (d[node][us]+ck)/2.0;
// if(!vis[it][us+1])pq.push({-d[it][us+1], {it, us+1}});
// vis[it][us+1] = true;
// }
}
}
double ans = 1e15;
bool f = false;
for(int i = 0; i <= K; i++)
{
if(d[H][i] == -1) continue;
ans = min(ans, d[H][i]);
f = true;
}
if(!f) ans = -1;
return ans;
}
int main()
{
int n, m, k, h;
cin >> n >> m >> k >> h;
vector<int>x(m), y(m), c(m), arr(n);
for(int j = 0; j < m; j++) cin >> x[j] >> y[j] >> c[j];
for(int i = 0; i < n; i++) cin >> arr[i];
cout << solve(n, m, k, h, x, y, c, arr);
}