#pragma GCC optimize("O3,unroll-loops") #include "cyberland.h" #include <bits/stdc++.h> using namespace std; vector<pair<int,int>> edges[100000]; 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) { for (int i=0;i<N;i++) edges[i].clear(); for (int i=0;i<M;i++) { edges[x[i]].push_back({y[i],c[i]}); edges[y[i]].push_back({x[i],c[i]}); } double dp[N][2]; for (int i=0;i<N;i++) { for (int j=0;j<2;j++) dp[i][j] = 2e18; } using wtf = pair<double,pair<int,int>>; priority_queue<wtf,vector<wtf>,greater<wtf>> pq; pq.push({0,{0,0}}); pq.push({0,{0,1}}); while (!pq.empty()) { wtf f = pq.top(); pq.pop(); double cost = f.first; int used = f.second.second; int city = f.second.first; if (dp[city][used] <= cost) continue; dp[city][used] = cost; for (auto it : edges[city]) { int dest = it.first; int go = it.second; if (!arr[dest]) { pq.push(make_pair(0,make_pair(dest,used))); } else if (arr[dest]) { pq.push({cost+go,{dest,used}}); } else { if (!used) pq.push({(cost+go)/pow(2,K),{dest,1}}); pq.push({cost+go,{dest,used}}); } } } return dp[H][1]; } int main() { int T; assert(1 == scanf("%d", &T)); while (T--){ int N,M,K,H; assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H)); std::vector<int> x(M); std::vector<int> y(M); std::vector<int> c(M); std::vector<int> arr(N); for (int i=0;i<N;i++) assert(1 == scanf("%d", &arr[i])); for (int i=0;i<M;i++) assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i])); printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr)); } }

/usr/bin/ld: /tmp/ccQIgUY6.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccXUsGT5.o:cyberland.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status