# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1228019 | jfioashfn333 | Cyberland (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
#include <set>
#include <queue>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define r0 return 0
using namespace std;
const int N = 1e6 + 5, M = 5001, MOD = 998244353, modu = 1e9 + 7;
int n, m, k, h;
int a[N];
vector<pii> g[N];
vector<int> x, y, z;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> k >> h;
for (int i = 0; i < n; i++) cin >> a[i];
x.resize(m); y.resize(m); z.resize(m);
for (int i = 0; i < m; i++) {
cin >> x[i] >> y[i] >> z[i];
g[x[i]].pb({y[i], z[i]});
g[y[i]].pb({x[i], z[i]});
}
vector<int> d(n, 1e18);
d[0] = 0;
priority_queue<pii, vector<pii>, greater<>> q;
q.push({0, 0});
while (!q.empty()) {
auto [w, u] = q.top(); q.pop();
if (w > d[u]) continue;
for (auto [v, c] : g[u]) {
int nw = d[u] + c;
if (a[v] == 0) nw = 0;
if (nw < d[v]) {
d[v] = nw;
q.push({nw, v});
}
}
}
if (d[h] == 1e18) cout << -1 << endl;
else cout << d[h] << endl;
return 0;
}