AT947 高橋君と国家 题解

Doveqise

2019-03-14 17:22:29

Solution

题目大意: 高桥君在游戏里运营着自己的国度。 他的国度有N个城市和M条道路。每条道路连结着2个不同的城市,途中没有其他的城市。另外,无论哪2个城市,直接连接这些城市的道路都有1条。 最初,没有铺设任何道路,并且任何城市都没有设置交易所。 高桥为了国度的发展,决定铺设道路和建造交易所。 所有的城市,只要满足以下任一条件,国家就称之为“良好状态”: - 那个城市设有交易所。 - 那个城市虽然没有设置交易所,但是通过从那个城市铺设的道路可以移动到设置交易所的其他城市。 城市的编号从1到N,街道的编号为1到M。在城市i设置交易所需要Ci枚金币,铺设道路i需要Ri枚金币。 因为没带太多金币,所以高桥君想尽可能减少把国家变成“良好状态”所必要的金币的枚数。 写一个程序,输出必要的金币枚数的最小值。 分析: 这道题就用一个优先队列维护一下两个城市之间道路和再建造一个交易所的pair,然后按照题意做即可. 详细操作见代码 ↓ ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; typedef pair<int,int>pa; const int INF=1234567890; struct edge{int to,weight;}; int main() { int N,M;scanf("%d%d",&N,&M); vector<vector<edge> >cost(N+1, vector<edge>(0)); for(int i=1;i<=N;i++) {int c;scanf("%d",&c);cost[0].push_back({i,c});} for(int i=1;i<=M;i++) { int a,b,r;scanf("%d%d%d",&a,&b,&r); cost[a].push_back({b,r}),cost[b].push_back({a,r});} priority_queue<pa, vector<pa>, greater<pa> > mincost; vector<bool>used(N+1,false); used[0]=0;mincost.push(pa(0,0)); ll ans=0; while(!mincost.empty()) { pa v=mincost.top();mincost.pop(); if(used[v.second])continue; used[v.second]=1;ans+=v.first; for(edge e:cost[v.second]) mincost.push(pa(e.weight, e.to)); } printf("%lld",ans); return 0; } ```