Codeforces Round #368 (Div. 2)（B. Bakery 贪心）

本文主要是介绍Codeforces Round #368 (Div. 2)（B. Bakery 贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

给出n个城市，m条道路，然后选择k个城市中的一个作为仓库，然后选择k个城市之外的一个城市作为商店，问这2个城市最短距离，图可能是不连通的，误解输出-1

直接贪心，遍历一遍k个城市，找到与之相连的且不是这k个城市之一的，最短的一个城市

#include<bits/stdc++.h>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define LL long long
#define pb push_back
#define gcd __gcd#define For(i,j,k) for(int i=(j);i<k;i++)
#define lowbit(i) (i&(-i))
#define _(x) printf("%d\n",x)const int maxn = 3e6+10;
const int inf  = 1 << 28;struct node{int x,y;LL w;int get(int u){if(u==x)return y;else return x;}
};vector<node> es;
vector<int> G[maxn];
void add(int from,int to,LL w){es.pb((node){from,to,w});int m = es.size()-1;G[from].pb(m);G[to].pb(m);
}bool vis[maxn];
vector<int> v;
int main(){int n,m,k;scanf("%d%d%d",&n,&m,&k);LL ans = 1LL<<62;for(int i=0;i<m;i++){int x,y;LL w;scanf("%d%d%lld",&x,&y,&w);add(x,y,w);}for(int i=0;i<k;i++){int x;scanf("%d",&x);v.pb(x);vis[x]=1;}for(int i=0;i<k;i++){int u = v[i];for(int j=0;j<G[u].size();j++){int id = G[u][j];int v = es[id].get(u);if(vis[v])continue;ans= min(ans,es[id].w);}}printf("%lld\n",ans==1LL<<62?-1:ans);return 0;
}

这篇关于Codeforces Round #368 (Div. 2)（B. Bakery 贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---