제출 #1329910

#제출 시각아이디문제언어결과실행 시간메모리
1329910tkm_algorithmsConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
6 ms580 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int NMAX = 2e5+10;
const int inf = NMAX*1e9;
vector<P> g[NMAX];
int n, m, s, t, l, k;
vector<int> djk(int src) {
	vector<int> d(n+1, inf); d[src] = 0;
	priority_queue<P, vector<P>, greater<P>> pq;
	pq.push(P(0, src));
	while (!pq.empty()) {
		auto [dist, nd] = pq.top(); pq.pop();
		if (d[nd] != dist)continue;
		for (auto [ch, w]: g[nd])
			if (dist+w < d[ch])
				d[ch] = dist+w,
				pq.push(P(dist+w, ch));
	}
	
	return d;
}

void solve() {
	cin >> n >> m >> s;
	cin >> t >> l >> k;
	
	rep(i, 0, m) {
		int a, b, c; cin >> a >> b >> c;
		g[a].push_back(P(b, c));
		g[b].push_back(P(a, c));
	}
	
	vector<int> ds = djk(s);
	vector<int> dt = djk(t);
	
	int res = 0;
	rep(v, 2, n+1) {
		rep(u, 1, v)
			if (ds[u]+l+dt[v] <= k || dt[u]+l+ds[v] <= k)res += 1;
	}
	cout << res;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...