Submission #310279

#	Time	Username	Problem	Language	Result	Execution time	Memory
310279		nicolaalexandra	Cities (BOI16_cities)	C++14	0 / 100	1087 ms	20776 KiB

cities

/// imi incerc si eu norocul csf
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000000000000LL
using namespace std;

vector <pair<int,int> > L[DIM],t[DIM];
priority_queue <pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > H;
long long dp[DIM];
int viz[DIM],fth[DIM],v[10];
struct muchie{
    int x,y,cost;
};
vector <muchie> mch;
int n,m,k,i,j,x,y,cost;

inline int cmp (muchie a, muchie b){
    return a.cost < b.cost;
}

inline int get_rad (int x){
    while (fth[x] > 0)
        x = fth[x];
    return x;
}

void dfs (int nod, int dest){
    viz[nod] = 1;
    if (nod == dest)
        return;

    for (auto it : t[nod]){
        int vecin = it.first, cost = it.second;
        mch.push_back({nod,vecin,cost});
        if (!viz[vecin])
            dfs (vecin,dest);
    }
}

void dist (int x, int y){

    int i;
    for (i=1;i<=n;i++){
        dp[i] = INF;
        t[i].clear();
    }

    dp[x] = 0;
    H.push(make_pair(0,x));

    while (!H.empty()){
        int nod = H.top().second;
        long long cost = H.top().first;
        H.pop();
        if (cost <= dp[nod]){

            for (auto it : L[nod]){
                int vecin = it.first; long long new_cost = it.second;
                if (dp[nod] + new_cost < dp[vecin]){
                    dp[vecin] = dp[nod] + new_cost;
                    H.push(make_pair(dp[vecin],vecin));
                    t[vecin].clear();
                    t[vecin].push_back(make_pair(nod,new_cost));
                } else {
                    if (dp[nod] + new_cost < dp[vecin])
                        t[vecin].push_back(make_pair(nod,new_cost));
                }}}}

    memset (viz,0,sizeof viz);
    dfs (y,x);

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k>>m;

    for (i=1;i<=k;i++)
        cin>>v[i];

    for (i=1;i<=m;i++){
        cin>>x>>y>>cost;
        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
    }

    for (i=1;i<=k;i++)
        for (j=i+1;j<=k;j++)
            dist (v[i],v[j]);

    sort (mch.begin(),mch.end(),cmp);
    memset (fth,-1,sizeof fth);

    long long sol = 0;
    for (auto it : mch){
        int x = it.x, y = it.y;
        int radx = get_rad (x), rady = get_rad (y);
        if (radx != rady){
            sol += it.cost;
            if (fth[radx] > fth[rady])
                swap (radx,rady);
            fth[radx] += fth[rady];
            fth[rady] = radx;
        }
    }

    cout<<sol;

    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26