제출 #969102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969102		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	66 ms	12884 KiB

cities

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;

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]);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n,k,m; cin >> n >> k >> m;
    memset(dist,0x3f,sizeof(dist));
    for(int i=0;i<k;++i){
        cin >> im[i];
        mp[im[i]]=i+1;
    }
    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=1e9,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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26