oj.uz

답안 #758954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758954 2023-06-15T15:12:39 Z roCatalyst Voting Cities (NOI22_votingcity) C++14
20 / 100
 14 ms 1244 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 100000000000000;

struct edge {
    int v;
    int weight;
};


int main() {
    int N, E, K;
    cin >> N >> E >> K;

    vector<int> T;
    for (int i = 0; i < K; i++) {
        int Ki;
        cin >> Ki;
        T.push_back(Ki);
    }

    vector<vector<edge>> AL (N);
    for (int i = 0; i < E; i++) {
        int U, V, C;
        cin >> U >> V >> C;
        AL[V].push_back({U,C});
    }

    map<int,ll> dist;
    map<int,bool> done;
    for (int i = 0; i < N; i++) {
        dist[i] = inf;
        done[i] = false;
    }

    using pli = pair<ll,int>;
    priority_queue<pli,vector<pli>,greater<pli>> pq;

    for (auto p = T.begin(); p != T.end(); p++) {
        pq.push({0,*p});
        dist[*p] = 0;
    }

    while (!pq.empty()) {
        auto [_,u] = pq.top();
        pq.pop();
        if (!done[u]) {
            for (edge& e: AL[u]) {
                if (dist[e.v] > dist[u] + e.weight) {
                    dist[e.v] = dist[u] + e.weight;
                    pq.push({dist[e.v],e.v});
                }
            }
            done[u] = true;
        }
    }

    /*
    for (int i = 0; i < N; i++) {
        cout << dist[i] << ' ';
    }
    cout << endl;*/

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        vector<int> P;
        int S;
        cin >> S;
        for (int i = 0; i < 5; i++) {
            int Pi;
            cin >> Pi;
            P.push_back(Pi); 
        }

        if (dist[S] == inf) {
            cout << -1 << endl;
        } else {
            cout << dist[S] << endl;
        }
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         auto [_,u] = pq.top();
      |              ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1108 KB Output is correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 12 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1108 KB Output is correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 12 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 11 ms 1164 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 11 ms 1064 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1108 KB Output is correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 12 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 11 ms 1164 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 11 ms 1064 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 14 ms 1244 KB Output is correct
12 Correct 8 ms 1072 KB Output is correct
13 Correct 11 ms 1108 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1108 KB Output is correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 12 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 1060 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 12 ms 1056 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1108 KB Output is correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 12 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 11 ms 1164 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 11 ms 1064 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 1060 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 12 ms 1056 KB Output is correct
14 Incorrect 11 ms 1108 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1108 KB Output is correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 12 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 11 ms 1164 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 11 ms 1064 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 14 ms 1244 KB Output is correct
12 Correct 8 ms 1072 KB Output is correct
13 Correct 11 ms 1108 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 8 ms 1060 KB Output is correct
17 Correct 7 ms 1108 KB Output is correct
18 Correct 12 ms 1056 KB Output is correct
19 Incorrect 11 ms 1108 KB Output isn't correct
20 Halted 0 ms 0 KB -