oj.uz

답안 #938767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938767 2024-03-05T14:10:51 Z vjudge1 Toll (BOI17_toll) C++17
0 / 100
 3000 ms 6172 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

struct Edge {
    int x, y, t;
    Edge(int xi, int yi, int ti):x(xi),y(yi),t(ti){}
};
struct Path {
    int i, c;
    Path(int ii, int ci):i(ii),c(ci){}
};
bool compare(Path a, Path b) {
    return a.c > b.i;
}

int k, n, m, q, x, y, t;
vector<vector<Edge>> graph;

signed main() {
    cin >> k >> n >> m >> q;
    graph = vector<vector<Edge>>(n);
    for(int i = 0; i < m; i++) {
        cin >> x >> y >> t;
        graph[x].push_back(Edge(x, y, t));
    }
    while(q--) {
        // djikstra from a to b
        cin >> x >> y;
        priority_queue<Path, vector<Path>, function<bool(Path, Path)>> pq(compare);
        vector<int> dist(n, LLONG_MAX);
        Path temp(0,0);
        pq.push(Path(x, 0));
        while(pq.size()) {
            temp = pq.top();
            pq.pop();
            //cout << temp.i << " " << temp.c << "\n";
            if(dist[temp.i] < temp.c) continue;
            dist[temp.i] = temp.c;
            for(auto j : graph[temp.i]) {
                if(temp.c + j.t < dist[j.y]) pq.push(Path(j.y, temp.c + j.t));
            }
        }
        if(dist[y] == LLONG_MAX) cout << "-1\n";
        else cout << dist[y] << "\n";
    }
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2830 ms 1212 KB Output is correct
8 Execution timed out 3053 ms 1592 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2830 ms 1212 KB Output is correct
8 Execution timed out 3053 ms 1592 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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