QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562219#1982. JoggingV-ioleTAC ✓28ms14092kbC++202.4kb2024-09-13 15:50:292024-09-13 15:50:30

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 15:50:30]
  • 评测
  • 测评结果:AC
  • 用时:28ms
  • 内存:14092kb
  • [2024-09-13 15:50:29]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'