oj.uz

답안 #968866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968866 2024-04-24T08:05:17 Z vjudge1 Cities (BOI16_cities) C++17
0 / 100
 108 ms 20936 KB 
#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){
            if(mp[j] && i!=mp[j]-1){
                mst.push_back({dist[i][j],{i,mp[j]-1}});
            }
        }
    }
    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;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     while(cnt<k-1 && run<mst.size()){
      |                      ~~~^~~~~~~~~~~

Subtask #1
0 / 22.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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