修练者
小T非常喜欢花 ，也很喜欢城市H,但是城市H的花店很少，因此小T打算在城市H开设一家外送花店。送花到某一个地点的时间与花店到该地点之间最短路径长度是成正比的，小T希望花店的地址选在离最远的顾客距离最近的地方。
花店的顾客分布在城市H的N 个建筑中，这N 个建筑通过恰好N 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小T的花店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。
现给定城市H的地图（道路分布及其长度），请找出最佳的花店选址，输出其与最远的顾客之间的距离。
输入描述 Input Description
输入文件foodshop.in第一行包含一个整数N，表示城市C中的建筑和道路数目。
接下来N行，每行3个整数，Ai，Bi，Li（1≤i≤N；Li>0），表示一条道路连接了建筑Ai与Bi，其长度为Li 。
输出描述 Output Description
输出文件foodshop.out仅包含一个实数，四舍五入保留恰好一位小数，表示最佳快餐店选址距离最远用户的距离。
注意：你的结果必须恰好有一位小数，小数位数不正确不得分。
样例输入 Sample Input
输入样例#1：
4
1 2 1
1 4 2
1 3 2
2 4 1
输入样例#2：
5
1 5 100
2 1 77
3 2 80
4 1 64
5 3 41
样例输出 Sample Output
输出样例#1：
2.0
输出样例#2：
109.0
数据范围及提示 Data Size & Hint
对于 10%的数据，N<=80,Li=1；
对于 30%的数据，N<=600，Li<=100；
对于 60% 的数据，N<=2000，Li<=10^9；
对于 100% 的数据，N<=10^5，Li<=10^9
王远哲在2018-10-22 19:28:36追加了内容
陶姐，救命
王远哲在2018-10-23 18:50:14追加了内容
没人吗？
王远哲在2018-10-23 19:01:11追加了内容
谁会？？？？？？？？？？？？？
王远哲在2018-10-24 18:59:09追加了内容
我骗你们来的
既然来了，解决一下
2976！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
多少天天天天天天天天天天天天天天天天天天天天天天天天天天了？？
陆神还不来，呜呜呜
我在加酷町豆，不信了！！！
能不能学一学7分题哩？？？？？
王远哲在2018-10-24 19:03:27追加了内容
我是在学习，看看要用什么算法解决。
有没有人能帮助我，
思路
算法
我就采纳他！！！！！
说话算话！！！！！！！！！！！！！！！！！！
王远哲在2018-10-24 19:04:15追加了内容
若会了，也不要AC机了
王远哲在2018-12-13 17:31:02追加了内容
Please hurry !!!!
资深天翼
nannan
修练者
昏
新手天翼
难
高级光能
你是刷分的！
高级光能
不会+1
高级守护
难
修练者
- int read()
- {
- int x = 0, f = 1; char ch = getchar();
- while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
- while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
- return x * f;
- }
- #define ll long long
- const int MAX = 110000;
- const ll inf = (1ll << 62);
- int n, cnt, fir[MAX];
- struct edge
- {
- int to, nxt;
- ll w;
- edge() {}
- edge(int v, int f, ll l) { to = v, nxt = f, w = l; }
- } e[MAX << 1];
- void addedge(int u, int v, int w)
- {
- e[++cnt] = edge(v, fir[u], w), fir[u] = cnt;
- e[++cnt] = edge(u, fir[v], w), fir[v] = cnt;
- }
- #define rep(i, u) for (int i = fir[u]; i; i = e[i].nxt)
- int sta[MAX], top, cir[MAX], cntx;
- ll len[MAX], b[MAX];
- ll dis[MAX], d[MAX];
- bool inst[MAX], oncir[MAX], vis[MAX], flag;
- void dfs_cir(int u, int fa, ll l)
- {
- if (flag) return;
- sta[++top] = u;
- len[top] = l;
- inst[u] = 1;
- rep(i, u)
- {
- if (e[i].to == fa) continue;
- if (inst[e[i].to])
- {
- int v = e[i].to;
- for (int j = top; j >= 1 && sta[j] != e[i].to; j--)
- cir[++cntx] = sta[j], oncir[sta[j]] = 1, b[cntx] = len[j];
- cir[++cntx] = e[i].to, oncir[e[i].to] = 1, b[cntx] = e[i].w;
- flag = 1;
- }
- else dfs_cir(e[i].to, u, e[i].w);
- }
- top--;
- inst[u] = 0;
- }
- void dp(int u, int fa)
- {
- rep(i, u)
- if (e[i].to != fa && !oncir[e[i].to])
- {
- int v = e[i].to;
- dp(v, u);
- d[u] = max(d[u], dis[u] + dis[v] + e[i].w);
- dis[u] = max(dis[u], dis[v] + e[i].w);
- d[u] = max(d[u], d[v]);
- }
- }
- ll ans = 0;
- ll f1[MAX], g1[MAX], f2[MAX], g2[MAX];
- int main()
- {
- n = read();
- for (int i = 1; i <= n; i++)
- {
- int u = read(), v = read(), w = read();
- addedge(u, v, w);
- }
- dfs_cir(1, 0, 0);
- for (int i = 1; i <= cntx; i++)
- dp(cir[i], 0), ans = max(ans, d[cir[i]]);
- ll sum = 0, maxn = 0, minn = inf, tmp = b[cntx];
- b[cntx] = 0;
- for (int i = 1; i <= cntx; i++)
- {
- sum += b[i - 1];
- f1[i] = max(f1[i - 1], sum + dis[cir[i]]);
- g1[i] = max(g1[i - 1], sum + dis[cir[i]] + maxn);
- maxn = max(maxn, dis[cir[i]] - sum);
- }
- sum = maxn = 0;
- for (int i = cntx; i >= 1; i--)
- {
- sum += b[i];
- f2[i] = max(f2[i + 1], sum + dis[cir[i]]);
- g2[i] = max(g2[i + 1], sum + dis[cir[i]] + maxn);
- maxn = max(maxn, dis[cir[i]] - sum);
- }
- for(int i = 1; i <= cntx; i++)
- minn = min(minn, max(f1[i] + f2[i + 1] + tmp, max(g1[i], g2[i + 1])));
- ans = max(ans, minn);
- printf("%.1lf", (double)ans / 2.0);
- return 0;
- }
