Submission #973998

#	Time	Username	Problem	Language	Result	Execution time	Memory
973998		canadavid1	Cities (BOI16_cities)	C++17	51 / 100	613 ms	262144 KiB

cities

#include <iostream>
#include <vector>
#include <queue>

using Cost = long long;

struct uf
{
private:
    std::vector<int> data;
    int find(int val)
    {
        if (data[val] < 0) return val;
        return data[val] = find(data[val]);
    }
public:
    uf(int s) : data(s,-1) {}
    bool same(int a, int b)
    {
        return find(a)==find(b);
    }
    bool unite(int a, int b)
    {
        a = find(a);
        b = find(b);
        if (a==b) return false;
        if (-data[a] < -data[b]) std::swap(a,b);
        if (data[a] == data[b]) data[a]--;
        data[b] = a;
        return true;
    }
};

struct road
{
    int a,b;
    Cost cost;
};
struct city
{
    bool important=false;
    std::vector<std::pair<int,Cost>> neigh;
    Cost dist_to_important[5];
    std::vector<Cost> dist_to_all;
};

template<typename F>
void dijkstra(int start,std::vector<city>& cities, F callback)
{
    std::priority_queue<std::pair<Cost,int>> q;
    std::vector<bool> visit(cities.size(),0);
    q.emplace(0,start);
    while(q.size())
    {
        auto[cost,node] = q.top();q.pop();
        cost = -cost;
        if (visit[node]) continue;
        visit[node] = true;
        callback(cities[node],cost);
        for(auto[n,c] : cities[node].neigh) q.emplace(-cost-c,n);
    }
}

int main()
{
    std::cin.tie(0)->sync_with_stdio(false);
    int n,k,m;
    std::cin >> n >> k >> m;
    uf uf(n);
    std::vector<road> roads(m);
    std::vector<city> cities(n);
    std::vector<int> important(k);
    for(auto& i : important) 
    {
        std::cin >> i; i--;
        cities[i].important = true;
    }
    for(auto& r : roads) 
    {
        std::cin >> r.a >> r.b >> r.cost; r.a--; r.b--;
        cities[r.a].neigh.emplace_back(r.b,r.cost);
        cities[r.b].neigh.emplace_back(r.a,r.cost);
    }
    for(int i = 0; i < k; i++)
        dijkstra(important[i],cities,[i](city& c,Cost cost) {c.dist_to_important[i]=cost;});
    
    Cost c = 1ll<<62;
    if(k==2)
    {
        c = cities[important[1]].dist_to_important[0];
    }
    else if(k==3)
    {
        for(auto& n : cities) c = std::min(c,n.dist_to_important[0]+n.dist_to_important[1]+n.dist_to_important[2]);
    }
    else
    {
        for(auto& c : cities) c.dist_to_all.assign(n,1ll<<62);
        for(int i = 0; i < n; i++)
            dijkstra(i,cities,[i](city& c,Cost cost){c.dist_to_all[i]=cost;});
        
        if (k==4)
        {
            for(auto n : {1,2,3})
            for(auto& a: cities)
            for(auto& b: cities)
            {
                Cost co = 0;
                co += a.dist_to_important[0];
                co += a.dist_to_important[n];
                co += a.dist_to_all[&b-cities.data()];
                for(int i = 1; i < 4; i++) if(i!=n)
                    co += b.dist_to_important[i];
                c = std::min(c,co);
            }
        }
        else
        {
            for(auto e : {0,1,2,3,4})
            {
                int h = e == 0;
                for(auto h2 : {1,2,3,4})
                {
                    if (h2 == h || h2 == e) continue;
                    for(auto& a : cities)
                    for(auto& b : cities)
                    for(auto& C : cities)
                    {
                        Cost co = 0;
                        co += a.dist_to_important[h];
                        co += a.dist_to_important[h2];
                        co += a.dist_to_all[&b-cities.data()];
                        co += b.dist_to_important[e];
                        co += b.dist_to_all[&C-cities.data()];
                        for(int i = 0; i < 5; i++) if(i != h && i != e && i != h2)
                            co += C.dist_to_important[i];
                        c = std::min(c,co);
                    }
                }
            }
        }
        
    }
    std::cout << c << "\n";
    

}


/*
    3 points: one virtual, star graph, Y
    4 points: two virtual: >-<
    5 points: three virtual: >+< (but only the up of the plus)

*/

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