Submission #1189947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189947		AlgorithmWarrior	Cities (BOI16_cities)	C++20	14 / 100	242 ms	17380 KiB

cities

#include <bits/stdc++.h>

using namespace std;

long long const INF=1e18;
int const MAX=100005;
int n,k,m;
int cities[7];
struct edge{
    int nod,len;
};
vector<edge>G[MAX];
long long dist[MAX][7];

void read(){
    cin>>n>>k>>m;
    int i;
    for(i=1;i<=k;++i)
        cin>>cities[i];
    for(i=1;i<=m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
}

struct path{
    int nod;
    long long dst;
};

class cmp{
public:
    bool operator()(path a,path b){
        return a.dst>b.dst;
    }
};

void dijkstra(int nod,int cnt){
    int i;
    for(i=1;i<=n;++i)
        dist[i][cnt]=INF;
    dist[nod][cnt]=0;
    priority_queue<path,vector<path>,cmp>pq;
    pq.push({nod,0});
    while(!pq.empty()){
        auto [nd,dst]=pq.top();
        pq.pop();
        if(dst!=dist[nd][cnt])
            continue;
        for(auto [vec,len] : G[nd])
            if(dist[vec][cnt]>dst+len){
                dist[vec][cnt]=dst+len;
                pq.push({vec,dist[vec][cnt]});
            }
    }
}

void dijkstra_driver(){
    int i;
    for(i=1;i<=k;++i)
        dijkstra(cities[i],i);
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

long long solve(){
    long long ans=INF;
    int i,j;
    for(i=1;i<=n;++i){
        long long sum=0;
        for(j=1;j<=k;++j)
            sum+=dist[i][j];
        minself(ans,sum);
    }
    vector<int>perm;
    for(i=1;i<=k;++i)
        perm.push_back(i);
    do{
        long long sum=0;
        for(i=0;i<(int)perm.size()-1;++i)
            sum+=dist[cities[perm[i+1]]][perm[i]];
        minself(ans,sum);
    }while(next_permutation(perm.begin(),perm.end()));
    return ans;
}

int main()
{
    read();
    dijkstra_driver();
    cout<<solve();
    return 0;
}

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