oj.uz

답안 #1006837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006837 2024-06-24T09:13:06 Z overwatch9 Toll (BOI17_toll) C++17
8 / 100
 3000 ms 7260 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 50001;
vector <pair <int, int>> adj[maxn];
ll dis[maxn];
int processed[maxn];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int K, N, M, O;
    cin >> K >> N >> M >> O;
    for (int i = 0; i < M; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        adj[a].push_back({b, t});
    }
    for (int o = 1; o <= O; o++) {
        int st, ed;
        cin >> st >> ed;
        fill(dis, dis + N + 1, 1e18);
        dis[st] = 0;
        priority_queue <pair <ll, int>> pq;
        pq.push({0, st});
        while (!pq.empty()) {
            int s = pq.top().second;
            pq.pop();
            if (processed[s] == o)
                continue;
            processed[s] = o;
            for (auto i : adj[s]) {
                if (dis[i.first] > dis[s] + i.second) {
                    dis[i.first] = dis[s] + i.second;
                    pq.push({-dis[i.first], i.first});
                }
            }
        }
        if (dis[ed] == 1e18)
            dis[ed] = -1;
        cout << dis[ed] << '\n';
    }
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3064 ms 4692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3042 ms 5288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 3 ms 1628 KB Output is correct
8 Correct 7 ms 1816 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 15 ms 4320 KB Output is correct
11 Correct 159 ms 5212 KB Output is correct
12 Correct 249 ms 6740 KB Output is correct
13 Correct 267 ms 7260 KB Output is correct
14 Correct 226 ms 5972 KB Output is correct
15 Correct 176 ms 4444 KB Output is correct
16 Correct 158 ms 4444 KB Output is correct

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 3 ms 1628 KB Output is correct
8 Correct 7 ms 1816 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 15 ms 4320 KB Output is correct
11 Correct 159 ms 5212 KB Output is correct
12 Correct 249 ms 6740 KB Output is correct
13 Correct 267 ms 7260 KB Output is correct
14 Correct 226 ms 5972 KB Output is correct
15 Correct 176 ms 4444 KB Output is correct
16 Correct 158 ms 4444 KB Output is correct
17 Execution timed out 3070 ms 5340 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3064 ms 4692 KB Time limit exceeded
2 Halted 0 ms 0 KB -