oj.uz

답안 #978089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
978089 2024-05-08T18:55:26 Z SeenSiravit Evacuation plan (IZhO18_plan) C++14
41 / 100
 4000 ms 27844 KB 
#include<bits/stdc++.h>

using namespace std;

const int mxN = 1e5 + 5;

int n,m,k;
vector<pair<int,int>> g[mxN];
vector<int> npp;

int dis[mxN];

void dijkstra(){
    for(int i=1;i<=n;i++) dis[i] = INT_MAX;

    priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>>> pq;

    for(auto node : npp){
        dis[node] = 0;
        pq.push({dis[node] , node});
    }

    while(!pq.empty()){
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();

        if(dis[u] < w) continue;

        for(auto [v , cost] : g[u] ){
            if(dis[v] > w + cost){
                dis[v] = w + cost;
                pq.push({dis[v] , v});
            }
        }
    }
}

int dis2[mxN];

void solve(int start_node , int end_node){
    for(int i=1;i<=n;i++) dis2[i] = 0;
    
    dis2[start_node] = dis[start_node];

    priority_queue<pair<int,int>> pq;
    pq.push({dis2[start_node] , start_node});

    while(!pq.empty()){
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();

        if(dis2[u] > w) continue;
        
        if(u == end_node){
            cout<< dis2[u] << "\n";
            return ;
        }

        for(auto [v , cost] : g[u]){
            if(dis2[v] < min(w , dis[v])){
                dis2[v] = min(w , dis[v]);
                pq.push({dis2[v] , v});
            }
        }
    }

    cout<< 0 << "\n";
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);

    cin>> n >> m;

    for(int i=0;i<m;i++){
        int u,v,w;
        cin>> u >> v >> w;

        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }

    cin>> k;

    npp.resize(k);
    for(int i=0;i<k;i++) cin>> npp[i];

    dijkstra();

    // for(int i=1;i<=n;i++) cout<< dis[i] << " ";
    // cout<< "\n";

    int q;
    cin>> q;

    while(q--){
        int start_node , end_node;
        cin>> start_node >> end_node;
        solve(start_node , end_node);
    }

    return 0;
}

Compilation message

plan.cpp: In function 'void dijkstra()':
plan.cpp:30:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         for(auto [v , cost] : g[u] ){
      |                  ^
plan.cpp: In function 'void solve(int, int)':
plan.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         for(auto [v , cost] : g[u]){
      |                  ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 18 ms 3480 KB Output is correct
3 Correct 18 ms 3476 KB Output is correct
4 Correct 1 ms 3252 KB Output is correct
5 Correct 18 ms 3252 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 2 ms 3416 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 18 ms 3472 KB Output is correct
13 Correct 2 ms 3668 KB Output is correct
14 Correct 2 ms 3420 KB Output is correct
15 Correct 2 ms 3420 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 18 ms 3480 KB Output is correct
3 Correct 18 ms 3476 KB Output is correct
4 Correct 1 ms 3252 KB Output is correct
5 Correct 18 ms 3252 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 2 ms 3416 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 18 ms 3472 KB Output is correct
13 Correct 2 ms 3668 KB Output is correct
14 Correct 2 ms 3420 KB Output is correct
15 Correct 2 ms 3420 KB Output is correct
16 Execution timed out 4016 ms 9232 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3416 KB Output is correct
10 Correct 1 ms 3160 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 13528 KB Output is correct
2 Correct 203 ms 26608 KB Output is correct
3 Correct 212 ms 26856 KB Output is correct
4 Correct 28 ms 8272 KB Output is correct
5 Correct 217 ms 26728 KB Output is correct
6 Correct 188 ms 26616 KB Output is correct
7 Correct 220 ms 26988 KB Output is correct
8 Correct 189 ms 26608 KB Output is correct
9 Correct 200 ms 26708 KB Output is correct
10 Correct 204 ms 26732 KB Output is correct
11 Correct 247 ms 26924 KB Output is correct
12 Correct 216 ms 26736 KB Output is correct
13 Correct 200 ms 26612 KB Output is correct
14 Correct 192 ms 26736 KB Output is correct
15 Correct 248 ms 27844 KB Output is correct
16 Correct 192 ms 26744 KB Output is correct
17 Correct 188 ms 26612 KB Output is correct
18 Correct 197 ms 26608 KB Output is correct
19 Correct 28 ms 8120 KB Output is correct
20 Correct 185 ms 26736 KB Output is correct
21 Correct 217 ms 27344 KB Output is correct
22 Correct 49 ms 10952 KB Output is correct
23 Correct 33 ms 8692 KB Output is correct
24 Correct 45 ms 10824 KB Output is correct
25 Correct 49 ms 10808 KB Output is correct
26 Correct 38 ms 8812 KB Output is correct
27 Correct 31 ms 8268 KB Output is correct
28 Correct 48 ms 10708 KB Output is correct
29 Correct 29 ms 8284 KB Output is correct
30 Correct 44 ms 10812 KB Output is correct
31 Correct 29 ms 8284 KB Output is correct

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 18 ms 3480 KB Output is correct
3 Correct 18 ms 3476 KB Output is correct
4 Correct 1 ms 3252 KB Output is correct
5 Correct 18 ms 3252 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 2 ms 3416 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 18 ms 3472 KB Output is correct
13 Correct 2 ms 3668 KB Output is correct
14 Correct 2 ms 3420 KB Output is correct
15 Correct 2 ms 3420 KB Output is correct
16 Execution timed out 4016 ms 9232 KB Time limit exceeded
17 Halted 0 ms 0 KB -