#include <bits/stdc++.h>
using namespace std;
//#define USACO
#define fi first
#define se second
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define ALL(v) (v).begin(), (v).end()
#define BIT(i) (1LL << (i))
#define MASK(x, i) (((x) >> (i)) & 1)
#define REP(i, v) for( __typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++ i)
#define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; -- i)
const string NAME = "BAITAP";
const string name = "";
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int mod = 998244353;
const int mxN = 2e5 + 5;
int N, M, S, T, L;
long long K;
vector<pair<int, int>> edge[mxN];
vector<vector<long long>> d(3, vector<long long> (mxN));
void init(void){
cin >> N >> M;
cin >> S >> T >> L >> K;
FOR(i, 1, M){
int u, v, w;
cin >> u >> v >> w;
edge[u].push_back(make_pair(v, w));
edge[v].push_back(make_pair(u, w));
}
}
void dijkstra(int s, int t){
FOR(i, 1, N) d[t][i] = INF;
d[t][s] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>> , greater<pair<long long, int>>> pq;
pq.push(make_pair(0, s));
while(pq.empty() == false){
pair<long long, int> cur = pq.top();
pq.pop();
if(d[t][cur.se] != cur.fi) continue;
for(pair<int, int> v : edge[cur.se]){
if(d[t][v.fi] > v.se + d[t][cur.se]) pq.push(make_pair(d[t][v.fi] = v.se + d[t][cur.se], v.fi));
}
}
}
void process(void){
dijkstra(S, 0);
dijkstra(T, 1);
if(d[0][T] <= K){
cout << 1LL * N * (N - 1) / 2;
return;
}
}
signed main(void){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen((NAME + ".INP").c_str(), "r", stdin);
freopen((NAME + ".OUT").c_str(), "w", stdout);
#elif defined(USACO)
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
#endif
init();
process();
cerr << "\nTime elapsed: " << TIME << "s.\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
11356 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
11352 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
11352 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
11356 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |