Submission #973992

#	Time	Username	Problem	Language	Result	Execution time	Memory
973992		canadavid1	Cities (BOI16_cities)	C++14	14 / 100	475 ms	33168 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];
};

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
    {
        
    }
    std::cout << c << "\n";
    

}

Compilation message (stderr)

cities.cpp: In function 'void dijkstra(int, std::vector<city>&, F)':
cities.cpp:54:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         auto[cost,node] = q.top();q.pop();
      |             ^
cities.cpp:59:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for(auto[n,c] : cities[node].neigh) q.emplace(-cost-c,n);
      |                 ^

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