| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1001173 | underwaterkillerwhale | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#ifdef ONLINE_JUDGE
#include "cyberland.h"
#endif
#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e13;
const int BASE = 137;
struct toEdge {
int v, w;
};
int n, m, K, H;
int a[N];
vector<toEdge> ke[N];
namespace sub1 {
double dist[N];
bool dd[3];
double solution() {
rep (i, 1, n) dist[i] = INF;
queue<int> Q; Q.push(1);
dd[1] = 1;
dist[1] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
iter (&id, ke[u]) {
int v = id.v, w = id.w;
double delta = dist[u] + w;
if (a[v] == 2 && K > 0) delta /= 2;
if (dist[v] > delta) {
dist[v] = delta;
if (!dd[v] && v != H) {
dd[v] = 1;
Q.push(v);
}
}
}
}
if (!dd[H]) return -1;
return dist[H];
}
}
namespace sub160907 {
struct Data {
ll u, val;
};
struct cmp {
bool operator () (Data A, Data B) { return A.val > B.val; }
};
double solution() {
return -1;
}
}
#ifdef ONLINE_JUDGE
#include "cyberland.h"
double solve (int _n, int _m, int _K, int _H, vector<int> _U, vector<int> _V, vector<int> _W, vector<int> _A) {
n = _n;
m = _m;
K = _K;
H = _H;
++H;
rep (i, 1, n) {
a[i] = _A[i - 1];
}
rep (i, 0, m - 1) {
int u = _U[i], v = _V[i], w = _W[i];
++u, ++v;
ke[u].push_back({v, w});
ke[v].push_back({u, w});
}
if (n <= 3 && K <= 30)
return sub1 :: solution();
}
#endif
void solution() {
cin >> n >> m >> K >> H;
++H;
rep (i, 1, n) cin >> a[i];
rep (i, 1, m) {
int u, v, w;
cin >> u >> v>> w;
++u, ++v;
ke[u].push_back({v, w});
ke[v].push_back({u, w});
}
cout << sub1 :: solution () <<"\n";
}
#ifndef ONLINE_JUDGE
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// file ("c");
int num_Test = 1;
cin >> num_Test;
while (num_Test--)
solution();
}
#endif // ONLINE_JUDGE
/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4
1
4 4 30
3
1 1 2 1
0 1 5
0 2 5
1 3 2
2 3 4
3 2
0 1 5
0 2 5
1
1 2
*/