oj.uz

Submission #969107

# Submission time Handle Problem Language Result Execution time Memory
969107 2024-04-24T13:53:34 Z vjudge1 Cities (BOI16_cities) C++17
14 / 100
 233 ms 26276 KB 
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;

#define int long long
vector<pair<int,int>> vec[100007];
vector<pair<int,pair<int,int>>> mst;
int im[10];
int dist[10][100007];
int parent[10];
map<int,int> mp;
void dijikstra(int x){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,im[x]});
    dist[x][im[x]]=0;
    int node,dis;
    while(!pq.empty()){
        node=pq.top().second;
        dis=pq.top().first;
        pq.pop();
        for(auto i:vec[node]){
            if(dis+i.first<dist[x][i.second]){
                dist[x][i.second]=dis+i.first;
                pq.push({dis+i.first,i.second});
            }
        }
    }
}

int findpar(int x){
    if(parent[x]==x) return x;
    else return parent[x]=findpar(parent[x]);
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n,k,m; cin >> n >> k >> m;
    for(int i=0;i<k;++i){
        cin >> im[i];
        mp[im[i]]=i+1;
        for(int j=0;j<=n;++j) dist[i][j]=1e18;
    }
    int a,b,c;
    for(int i=0;i<m;++i){
        cin >> a >> b >> c;
        vec[a].push_back({c,b});
        vec[b].push_back({c,a});
    }
    for(int i=0;i<k;++i) dijikstra(i);
    /*
    for(int i=0;i<k;++i){
        for(int j=1;j<=n;++j){
            cout << dist[i][j] << " ";
            if(mp[j] && i!=mp[j]-1){
                mst.push_back({dist[i][j],{i,mp[j]-1}});
                //cout << "S" << i << " " << mp[j]-1 << " " << dist[i][j] << endl;
            }
        }
        cout << endl;
    }
    sort(mst.begin(),mst.end());
    int cnt=0,run=0;
    int u,v,w;
    int ans=0;
    for(int i=0;i<k;++i) parent[i]=i;
    while(cnt<k-1 && run<mst.size()){
        u=mst[run].second.first;
        v=mst[run].second.second;
        w=mst[run].first;
        int rootu=findpar(u);
        int rootv=findpar(v);
        if(rootu!=rootv){
            parent[rootu]=rootv;
            ++cnt;
            ans+=w;
            //cout << w << endl;
        }
        ++run;
    }
    cout << ans;
    */
    int mans=1e18,cur;
    for(int j=1;j<=n;++j){
        cur=0;
        for(int i=0;i<k;++i){
            cur+=dist[i][j];
        }
        mans=min(cur,mans);
    }
    cout << mans;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6232 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Incorrect 2 ms 8284 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 20700 KB Output is correct
2 Correct 177 ms 26276 KB Output is correct
3 Correct 51 ms 15824 KB Output is correct
4 Correct 61 ms 18804 KB Output is correct
5 Correct 142 ms 22916 KB Output is correct
6 Correct 51 ms 18772 KB Output is correct
7 Correct 5 ms 6492 KB Output is correct
8 Correct 2 ms 6368 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 20800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 233 ms 20692 KB Output isn't correct
2 Halted 0 ms 0 KB -