比赛 不平凡的世界 评测结果 AAAAAAAAAA
题目名称 不平凡的引线 最终得分 100
用户昵称 膜拜神犇王梦迪 运行时间 0.834 s
代码语言 C++ 内存使用 2.00 MiB
提交时间 2015-11-05 11:48:45
显示代码纯文本
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <queue>
  4. #include <vector>
  5. using namespace std;
  6. const int kN = 1e5+10;
  7. const int INF = 1e9+10;
  8. int N;
  9. vector<pair<int, int> > G[kN];
  10. int d[kN], vis[kN];
  11. int main() {
  12. freopen("firelead.in", "r", stdin);
  13. freopen("firelead.out", "w", stdout);
  14. scanf("%d", &N);
  15. N++;
  16. for (int i = 2; i <= N; i++) {
  17. int u, v, c; scanf("%d %d %d", &u, &v, &c);
  18. G[u].push_back(make_pair(v, c));
  19. G[v].push_back(make_pair(u, c));
  20. }
  21. priority_queue<pair<int, int> > q;
  22. for (int i = 1; i <= N; i++) {
  23. if (G[i].size() == 1) {
  24. q.push(make_pair(0, i));
  25. d[i] = 0;
  26. } else {
  27. d[i] = INF;
  28. }
  29. }
  30. while (q.size()) {
  31. int u = q.top().second;
  32. q.pop();
  33. if (vis[u]) continue;
  34. vis[u] = true;
  35. for (int i = 0; i < G[u].size(); i++) {
  36. int v = G[u][i].first, c = G[u][i].second;
  37. if (d[v] > d[u]+c) {
  38. d[v] = d[u]+c;
  39. q.push(make_pair(-d[v], v));
  40. }
  41. }
  42. }
  43. double ans = 0;
  44. for (int i = 1; i <= N; i++) {
  45. for (int j =0; j < G[i].size(); j++) {
  46. int v = G[i][j].first;
  47. double c = G[i][j].second;
  48. double mi = min(d[i], d[v]), mx = max(d[i], d[v]);
  49. // 整个引线烧完的时间 = 最近的点引燃 + 一个端点燃烧的时间 + 两个端点燃烧的时间
  50. double tmp = mi + min(c, mx-mi) + (c-min(c, mx-mi))/2;
  51. ans = max(ans, max(mx, tmp));
  52. }
  53. }
  54. printf("%.1lf\n", ans);
  55. return 0;
  56. }