Submission #1087553

#TimeUsernameProblemLanguageResultExecution timeMemory
1087553HienTDConstruction Project 2 (JOI24_ho_t2)C++14
0 / 100
5 ms11356 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...