QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#409649#1982. Joggingsgweo8ysWA 1ms3932kbC++141.5kb2024-05-12 14:10:312024-05-12 14:10:32

Judging History

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

  • [2024-05-12 14:10:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3932kb
  • [2024-05-12 14:10:31]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200010;
const int M = 200010;
const int inf = 1e17;

struct node{
    int u, dist;
    bool operator <(const node a)const{
        return dist > a.dist;
    }
};

int n, m, s, L, cnt, dis[N], head[N], nxt[M], to[M], w[M], vis[N];

int U[N], V[N];

priority_queue <node> q;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void addedge(int u, int v, int k)
{
    to[++cnt] = v, w[cnt] = k;
    nxt[cnt] = head[u], head[u] = cnt;
}

void dijkstra()
{
    for(int i = 0; i <= n; i++) dis[i] = inf;
    dis[s] = 0, q.push((node){s, 0});
    while(!q.empty()){
        node now = q.top(); q.pop();
        if(vis[now.u]) continue;
        vis[now.u] = 1;
        for(int i = head[now.u]; i; i = nxt[i]){
            int v = to[i];
            if(dis[v] > dis[now.u] + w[i])
                dis[v] = dis[now.u] + w[i], q.push((node){v, dis[v]});
        }
    }
}

signed main()
{
    n = read(), m = read(), s = read(), L = read();
    s = 0;
    for(int i = 1, u, v, k; i <= m; i++){
        u = read(), v = read(), k = read();
        U[i] = u, V[i] = v;
        addedge(u, v, k);
    }
    dijkstra();
    int ans = 0;
    for(int i = 1; i <= m; i++){
        if(2 * min(dis[U[i]], dis[V[i]]) < L) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3704kb

input:

1 0 1 1

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

2 1 5 10
0 1 3

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

2 1 10 12
0 1 13

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3760kb

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: 3704kb

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: 3860kb

input:

3 2 6 12
0 1 3
1 2 3

output:

2

result:

ok single line: '2'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3932kb

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: 0ms
memory: 3932kb

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: 3720kb

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: 3808kb

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: 3932kb

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: 0ms
memory: 3712kb

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: -100
Wrong Answer
time: 0ms
memory: 3712kb

input:

3 2 6 12
2 1 4
1 0 2

output:

1

result:

wrong answer 1st lines differ - expected: '2', found: '1'