| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1322217 | norrawichzzz | Construction Project 2 (JOI24_ho_t2) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
const int INF = 4e18;
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int n,m;
cin>> n>> m;
int s,t,l,k;
cin>> s>> t>> l>> k;
vector<vector<pair<int,int>>> g(n+1);
for (int i=0; i<m; i++) {
int u,v,w;
cin>> u>> v>> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
vector<int> dist(n+1, INF), rdist(n+1, INF);
dist[s] = 0;
rdist[t] = 0;
priority_queue<pi, vector<pi>, greater<pi>> pq;
pq.push({0, s});
while (!pq.empty()) {
int u=pq.top().second, d=pq.top().first;
pq.pop();
if (dist[u] < d) continue;
for (auto &x : g[u]) {
int v=x.first, w=x.second;
if (dist[v] > dist[u]+w) {
dist[v] = dist[u]+w;
pq.push({dist[v], v});
}
}
}
pq.push({0, t});
while (!pq.empty()) {
int u=pq.top().second, d=pq.top().first;
pq.pop();
if (rdist[u] < d) continue;
for (auto &x : g[u]) {
int v=x.first, w=x.second;
if (rdist[v] > rdist[u]+w) {
rdist[v] = rdist[u]+w;
pq.push({rdist[v], v});
}
}
}
int ans = 0;
for (int i=1; i<=n; i++) {
for (int j=i+1; j<=n; j++) {
if (dist[i] + l + rdist[j] <= k) ans++;
else if (rdist[i] + l + dist[j] <= k) ans++;
else if (dist[j] + l + rdist[i] <= k) ans++;
else if (rdist[j] + l + dist[i] <= k) ans++;
else if (dist[e]<=k || rdist[s] <= k) ans++;
}
}
cout<< ans;
}