修练者
小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 !!!!
初级天翼
二叉树，你要遍历再去搜
中级光能
太难了
高级守护
我会
缔造者
为啥我没有这一题
高级天翼
哇！你是我见过最牛的人
初级守护
太难了，不会。建议打好基础，在做。你也可以问老师获得一些思路
资深天翼
难，我是弱鸡
新手守护
这道题很难，建议打好基础在做
中级光能
这道题涉及到有关二叉树的知识了，所以建议你把基础打牢再做，否则做起来很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲（*10000000000000000000000000000000000000）
中级光能
earsds
高级守护
这道题非常难，建议先打牢基础
资深光能
这题太难了
新手天翼
#include <bits/stdc++.h>
using namespace std;
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;
}王兄，你看，这个贴那么久都没人，我趁乱发个整段代码没事吧！（发伪代码怕你看不懂，这个也是我抄的，哈哈），别举报，求采纳！
初级光能
还可以，有方法做
王泽宇在2020-07-20 11:50:11追加了内容
查360
初级启示者
无论你是基础班还是提高班，建议你不要做
中级天翼
难
中级启示者
有这题吗？？？我为啥没搜到
高级守护
M.png)
新手天翼
我们的这个贴出名了！
新手光能
顶
新手天翼
难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难
初级天翼
这道题非常难，建议先打牢基础，这道题在酷町堂不是一般人能做出来的！（陆大神也不一定）
新手光能
二叉树
初级光能
太难了，先打好基础，不要只想刷题！
中级光能
难的话问老师不就行了？？？？？？？
新手光能
这道题非常难，建议先打牢基础在做
资深守护
难！
中级天翼
不会
中级天翼
李锦昊
2400
Accepted：100分
李锦昊的测评结果：
测试点
结果
时间
1
Accepted
4ms
偷看一下数据
2
Accepted
0ms
偷看一下数据
3
Accepted
0ms
偷看一下数据
4
Accepted
0ms
偷看一下数据
5
Accepted
0ms
偷看一下数据
6
Accepted
16ms
偷看一下数据
7
Accepted
20ms
偷看一下数据
8
Accepted
4ms
偷看一下数据
9
Accepted
4ms
偷看一下数据
10
Accepted
0ms
偷看一下数据
已AC
资深守护
难
新手天翼
资深光能
难！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
资深光能
int main()
{
int a,b;
cin>>a>>b;
cout<<a+b;
} 陈喆鹏在2018-10-18 20:14:04追加了内容
看成1976了
新手天翼
陆神已经隐退了
资深守护
-
void adde(int a,int b,int c)
-
{
-
to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;cd[cnt]=c;
-
to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;cd[cnt]=c;
-
}
-
#define LL long long
-
int cir[N],D[N],fa[N],dep[N];
-
bool vis[N];
-
void findcir(int u)
-
{
-
dep[u]=dep[fa[u]]+1;
-
int v,p;
-
for(p=fir[u];p;p=nxt[p]){
-
v=to[p];
-
if(v==fa[u]) continue;
-
if(!dep[v]){fa[v]=u;findcir(v);}
-
else if(dep[v]<dep[u]){
-
for(int j=u;;j=fa[j]){
-
vis[j]=1;cir[++m]=j;
-
if(j==v)break;
-
}
-
}
-
}
-
}
-
LL hei[N],ans;
-
void dfs(int u)
-
{
-
int v,p,w;
-
for(p=fir[u];p;p=nxt[p]){
-
v=to[p];w=cd[p];
-
if(v!=fa[u]&&!vis[v]){
-
dfs(v);
-
ans=max(hei[u]+hei[v]+w,ans);
-
hei[u]=max(hei[u],hei[v]+w);
-
}
-
}
-
}
-
LL g1[N],g2[N],h1[N],h2[N];
-
int main()
-
{
-
int n,i,u,v,w,p;
-
scanf("%d",&n);
-
for(i=1;i<=n;i++){
-
scanf("%d%d%d",&u,&v,&w);
-
adde(u,v,w);
-
}
-
findcir(1);
-
for(i=1;i<=n;i++)
-
if(vis[i]) dfs(i);
-
cir[m+1]=cir[1];
-
for(i=1;i<=m;i++)
-
for(p=fir[cir[i]];p;p=nxt[p])
-
if(to[p]==cir[i+1]){
-
D[i]=cd[p];
-
break;
-
}
-
LL sum=0,mx=hei[cir[1]]+D[1];
-
for(i=2;i<=m;i++){
-
sum+=D[i-1];
-
h1[i]=max(h1[i-1],hei[cir[i]]+sum);
-
g1[i]=max(g1[i-1],hei[cir[i]]+mx);
-
mx=max(mx,hei[cir[i]])+D[i];
-
}
-
sum=0;mx=hei[cir[1]]+D[m];
-
for(i=m;i>1;i--){
-
sum+=D[i];
-
h2[i]=max(h2[i+1],hei[cir[i]]+sum);
-
g2[i]=max(g2[i+1],hei[cir[i]]+mx);
-
mx=max(mx,hei[cir[i]])+D[i-1];
-
}
-
LL ret=1ll<<60;
-
for(i=1;i<=m;i++)
-
ret=min(ret,max(ans,max(h1[i]+h2[i+1],max(g1[i],g2[i+1]))));
-
printf("%.1f",1.0*ret/2);
修练者
纳闷
新手守护
找陆大佬
资深守护
这题太难啦
新手光能
cout<<"2.0";
资深光能
先打好基础，这题太难了。
中级光能
新手天翼
这道题有一个简单思路，就是贪心……（不用谢我，叫我雷锋）
新手天翼
这道题有一个简单思路，就是贪心……（不用谢我，叫我雷锋）
资深光能
问老师
中级天翼
额
高级守护
大家都不会
资深守护
难，我不会！有谁
出来看看
初级天翼
wafenle
难
初级光能
难！
修练者
难！ 难！
难！难！ 难！难！难！
难！ 难！ 难！ 难！ 难！ 难！
难！ 难！ 难！ 难！ 难！难！难！
难！ 难！ 难！
难！ 难！ 难！ 难！难！难！
难！ 难！
难！ 难！难！难！
