#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <cmath>
using namespace std;
struct Edge {
int to;
double cost;
};
struct State {
int node;
double cost;
int divides_used;
bool operator>(const State& other) const {
return cost > other.cost;
}
};
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<Edge>> adj(N);
for (int i = 0; i < M; ++i) {
adj[x[i]].emplace_back(Edge{y[i], static_cast<double>(c[i])});
adj[y[i]].emplace_back(Edge{x[i], static_cast<double>(c[i])});
}
priority_queue<State, vector<State>, greater<State>> pq;
vector<vector<double>> dist(N, vector<double>(K + 1, numeric_limits<double>::infinity()));
pq.push({0, 0, 0});
dist[0][0] = 0;
while (!pq.empty()) {
State current = pq.top();
pq.pop();
int node = current.node;
double cost = current.cost;
int divides_used = current.divides_used;
if (node == H) {
return cost;
}
if (cost > dist[node][divides_used]) {
continue;
}
for (const Edge& edge : adj[node]) {
int next_node = edge.to;
double next_cost = cost + edge.cost;
if (next_cost < dist[next_node][divides_used]) {
dist[next_node][divides_used] = next_cost;
pq.push({next_node, next_cost, divides_used});
}
if (arr[next_node] == 0 && 0 < dist[next_node][divides_used]) {
dist[next_node][divides_used] = 0;
pq.push({next_node, 0, divides_used});
}
if (arr[next_node] == 2 && divides_used < K) {
double divided_cost = cost / 2.0;
if (divided_cost < dist[next_node][divides_used + 1]) {
dist[next_node][divides_used + 1] = divided_cost;
pq.push({next_node, divided_cost, divides_used + 1});
}
}
}
}
return -1;
}
int main() {
int T;
cin >> T;
while (T--) {
int N, M, K;
cin >> N >> M >> K;
int H;
cin >> H;
vector<int> arr(N);
for (int i = 0; i < N; ++i) {
cin >> arr[i];
}
vector<int> x(M), y(M), c(M);
for (int i = 0; i < M; ++i) {
cin >> x[i] >> y[i] >> c[i];
}
double result = solve(N, M, K, H, x, y, c, arr);
if (result == -1) {
cout << result << endl;
} else {
printf("%.10f\n", result);
}
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc1ski2E.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccUiZ62C.o:cyberland.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
