QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562219 | #1982. Jogging | V-ioleT | AC ✓ | 28ms | 14092kb | C++20 | 2.4kb | 2024-09-13 15:50:29 | 2024-09-13 15:50:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define ull unsigned long long
typedef long long ll;
#define lowbit(x) ((x) & -(x))
const ll INF = 0x3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 5, M = 5e5 + 10;
typedef pair<int, int> PII;
double T = 1 >> 30;
// double PI = acos(-1);
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
struct edge
{
int v, w;
};
vector<edge> e[N];
// void print_path(int s, int t)
// {
// if (s == t)
// {
// printf("%d", s);
// return;
// }
// print_path(s, pre[t]);
// printf("->%d", t);
// }
struct node
{
int id, dis;
node(int a, int b)
{
id = a;
dis = b;
}
bool operator<(const node &u) const
{
return dis > u.dis;
}
};
int dist[N];
bool done[N];
void dij()
{
for (int i = 0; i < N; i++)
{
dist[i] = INF;
done[i] = 0;
}
dist[0] = 0;
priority_queue<node> q;
q.push({0, 0});
while (!q.empty())
{
node u = q.top();
q.pop();
if (done[u.id])
continue;
done[u.id] = 1;
for (int i = 0; i < e[u.id].size(); i++)
{
int v = e[u.id][i].v, w = e[u.id][i].w;
if (done[v])
{
continue;
}
if (dist[v] > u.dis + w)
{
dist[v] = u.dis + w;
q.push({v, dist[v]});
}
}
}
}
void solve()
{
int i, j;
int n, m, l, r;
cin >> n >> m >> l >> r;
vector<PII> vec;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
vec.push_back({u, v});
e[u].push_back({v, w});
e[v].push_back({u, w});
}
dij();
int ans = 0;
for (i = 0; i < vec.size(); i++)
{
int mn = min(dist[vec[i].first], dist[vec[i].second]);
if (2 * mn < r)
{
ans++;
}
}
cout << ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
// system("pause");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5284kb
input:
1 0 1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5428kb
input:
2 1 5 10 0 1 3
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5324kb
input:
2 1 10 12 0 1 13
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5304kb
input:
3 2 1 2 0 1 3 1 2 3
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5396kb
input:
3 2 6 6 0 1 3 1 2 3
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
3 2 6 12 0 1 3 1 2 3
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5364kb
input:
3 3 9 9 0 1 3 1 2 3 0 2 3
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5324kb
input:
3 3 1 7 0 1 3 1 2 3 0 2 3
output:
3
result:
ok single line: '3'
Test #9:
score: 0
Accepted
time: 0ms
memory: 5228kb
input:
3 3 1 6 0 1 3 1 2 3 0 2 3
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5288kb
input:
3 3 1 2 0 1 3 1 2 3 0 2 3
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5280kb
input:
4 5 100 120 0 1 1 0 2 1 0 3 1 1 2 1 2 3 1
output:
5
result:
ok single line: '5'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5628kb
input:
4 5 4 4 0 1 2 0 2 2 0 3 1 1 2 1 2 3 1
output:
4
result:
ok single line: '4'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5332kb
input:
3 2 6 12 2 1 4 1 0 2
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5332kb
input:
3 2 1 2 1 0 3 2 1 3
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5452kb
input:
3 2 6 6 2 1 1 1 0 5
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 24ms
memory: 14092kb
input:
100000 100000 10290 42195 0 1 215 0 2 880 0 4 687 0 11 39 0 55 535 0 72 855 1 3 30 1 6 858 1 9 103 1 10 38 1 18 77 1 26 126 1 69 20 2 5 351 2 12 922 2 14 588 2 27 943 2 48 463 3 35 1000 3 38 704 3 50 986 3 67 639 4 8 357 4 20 305 5 7 96 6 16 262 6 82 971 9 21 581 9 90 149 10 13 353 10 15 984 10 23 5...
output:
1851
result:
ok single line: '1851'
Test #17:
score: 0
Accepted
time: 23ms
memory: 13936kb
input:
100000 100000 17806 42195 0 1 583 0 3 925 0 6 37 0 117 151 0 847 567 1 2 903 1 4 604 1 20 386 1 123 480 1 242 45 2 5 607 2 9 559 2 17 306 2 132 267 2 261 82 2 495 479 3 7 711 3 36 127 4 8 738 4 24 979 4 96 287 4 121 498 4 231 869 4 247 947 4 279 40 5 15 317 5 176 755 5 313 934 5 365 321 5 611 307 6 ...
output:
18825
result:
ok single line: '18825'
Test #18:
score: 0
Accepted
time: 28ms
memory: 14000kb
input:
95000 100000 27047 42195 0 1 293 0 2 995 1 3 590 1 7 25 2 4 841 2 11 894 3 6 384 3 13 793 4 5 216 4 9 720 5 8 644 5 10 482 5 14 117 8 16 57 10 12 474 12 18 430 13 17 247 14 15 424 14 21 170 14 23 460 15 19 351 15 22 734 19 20 923 21 27 460 23 24 959 23 25 309 23 29 516 24 31 452 24 33 891 25 26 644 ...
output:
95558
result:
ok single line: '95558'