#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
bool vis[N];
ll dis[2][N];
pair<ll, int> ds[N], dt[N];
vector<pair<int, ll>> ed[N];
vector<int> que[N];
pair<int, int> pos[N], q[N];
int drz[2 * N];
void Add(int v)
{
v += N;
while(v > 0)
{++drz[v]; v /= 2;}
}
int Query(int a, int b)
{
a += N - 1; b += N + 1;
int ans = 0;
while(a / 2 != b / 2)
{
if(a % 2 == 0) ans += drz[a + 1];
if(b % 2 == 1) ans += drz[b - 1];
a /= 2; b /= 2;
}
return ans;
}
void Dijkstra(int r, int s, int n)
{
int v;
priority_queue<pair<ll, int>> q;
for(int i = 1; i <= n; ++i)
{dis[r][i] = I; vis[i] = false;}
dis[r][s] = 0LL;
q.push(make_pair(0, s));
while((int)q.size() > 0)
{
v = q.top().nd; q.pop();
if(vis[v]) continue;
vis[v] = true;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
ll o = dis[r][v] + ed[v][i].nd;
if(o < dis[r][ed[v][i].st])
{
dis[r][ed[v][i].st] = o;
q.push(make_pair(-o, ed[v][i].st));
}
}
}
}
void Solve()
{
int n, m, a, b, s, t, l, c;
ll k;
ll ans = 0LL;
scanf("%d %d", &n, &m);
scanf("%d %d %d %lld", &s, &t, &l, &k);
for(int i = 1; i <= m; ++i)
{
scanf("%d %d %d", &a, &b, &c);
ed[a].pb(make_pair(b, c));
ed[b].pb(make_pair(a, c));
}
Dijkstra(0, s, n);
Dijkstra(1, t, n);
if(dis[0][t] <= k)
{
printf("%lld\n", ((ll)n * (ll)(n - 1)) / 2LL);
return;
}
for(int i = 1; i <= n; ++i)
{
ds[i] = make_pair(dis[0][i], i);
dt[i] = make_pair(dis[1][i], i);
}
sort(ds + 1, ds + 1 + n);
sort(dt + 1, dt + 1 + n);
int j = n;
for(int i = 1; i <= n; ++i)
{
while(j > 0 && ds[i].st + dt[j].st + (ll)l > k)
--j;
ans += (ll)j;
q[ds[i].nd].nd = j;
pos[ds[i].nd].st = i;
}
j = n;
for(int i = 1; i <= n; ++i)
{
while(j > 0 && ds[j].st + dt[i].st + (ll)l > k)
--j;
ans += (ll)j;
q[dt[i].nd].st = j;
pos[dt[i].nd].nd = i;
}
for(int i = 1; i <= n; ++i)
{
if(q[i].st >= pos[i].st && q[i].nd >= pos[i].nd) --ans;
if(q[i].st >= pos[i].st) --ans;
if(q[i].nd >= pos[i].nd) --ans;
que[q[i].st].pb(q[i].nd);
}
sort(pos + 1, pos + 1 + n);
for(int i = 1; i <= n; ++i)
{
Add(pos[i].nd);
for(j = 0; j < (int)que[pos[i].st].size(); ++j)
ans -= (ll)Query(1, que[pos[i].st][j]);
}
ans /= 2LL;
printf("%lld\n", ans);
}
int main()
{
//int t; cin >> t;
//while(t--)
Solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void Solve()':
Main.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d %d %d %lld", &s, &t, &l, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d %d %d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |