Submission #1164174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164174		KhoaDuy	Board Game (JOI24_boardgame)	C++17	3 / 100	23 ms	4492 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<int> dijik(int n,vector<vector<int>> &graph,vector<int> &init){
    vector<int> bst(n+1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=1;i<=n;i++){
        pq.push({init[i],i});
        bst[i]=init[i];
    }
    while(!pq.empty()){
        int u=pq.top().second,dist=pq.top().first;
        pq.pop();
        if(dist>bst[u]){
            continue;
        }
        for(int v:graph[u]){
            if(bst[v]>dist+1){
                bst[v]=dist+1;
                pq.push({bst[v],v});
            }
        }
    }
    return bst;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<int>> graph(n+1);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    string s;
    cin >> s;
    int x[k];
    vector<int> init(n+1);
    for(int i=1;i<=n;i++){
        init[i]=1e9;
    }
    for(int i=0;i<k;i++){
        cin >> x[i];
    }
    init[x[0]]=0;
    vector<int> bst=dijik(n,graph,init);
    for(int i=1;i<=n;i++){
        cout << bst[i] << endl;
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 9
• Subtask 7: 0 / 23
• Subtask 8: 0 / 9