首页 > 代码库 > Codeforces 707B. Bakery
Codeforces 707B. Bakery
题目链接:http://codeforces.com/problemset/problem/707/B
题意:
给你一个含有 n 个点, m 条边的无向带权图,以及 k 个点, 这 n 个点代表着 n 个城市, 边和权值代表着两个城市之间的路以及距离, k 个点代表着 n 个城市中有 k 个城市有面包店, 某人站在没有面包店的某个城市, 问你他到具有面包店的城市的最短距离.
思路:
把这 m 条边按照权值从小到大排序,然后依次检查每条边的两个端点,如果满足其中一个具有面包点,且其另外一个不具有,那么最短距离就是最先找到的那个.
代码:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int MAXN = 100000; 6 typedef long long LL; 7 8 struct NODE { int u;int v; int l;} ; 9 NODE edge[MAXN + 3];10 11 int cmp(NODE a, NODE b) { return a.l < b.l; }12 13 int main() {14 ios_base::sync_with_stdio(0); cin.tie(0);15 int n, m, k; cin >> n >> m >> k;16 int back[MAXN + 3];17 for(int i = 0; i < m; i++) cin >> edge[i].u >> edge[i].v >> edge[i].l;18 for(int i = 0; i < k; i++) cin >> back[i];19 sort(edge, edge + m, cmp);20 sort(back, back + k);21 int ans = -1;22 for(int i = 0; i < m; i++) {//从最短的开始检查23 int flag1 = lower_bound(back, back + k, edge[i].u) - back;24 int flag2 = lower_bound(back, back + k, edge[i].v) - back;25 if(back[flag1] == edge[i].u && back[flag2] != edge[i].v || back[flag1] != edge[i].u && back[flag2] == edge[i].v) {//是否满足一个具有面包店,另外一个不具有26 ans = edge[i].l;27 break;28 }29 }30 cout << ans << endl;31 return 0;32 }
Codeforces 707B. Bakery
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。