问题标题: 2976求提示，哪怕一点点也采

2
1
王远哲
王远哲
修练者
修练者

小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 !!!!

举报

80酷町豆 刷题求解 7条评论 5 年，11 月 前

1
张睿杰
张睿杰
初级天翼
初级天翼

二叉树，你要遍历再去搜

阅读更多
举报

5 年，11 月 前 1条评论

0
0
0
0
潘晨皓
潘晨皓
高级天翼
高级天翼

哇！你是我见过最牛的人

阅读更多
举报

4 年，8 月 前 1条评论

0
吕嘉莹
吕嘉莹
初级守护
初级守护

太难了，不会。建议打好基础，在做。你也可以问老师获得一些思路

阅读更多
举报

4 年，3 月 前 1条评论

0
0
尹宗鑫
尹宗鑫
新手守护
新手守护

这道题很难，建议打好基础在做

阅读更多
举报

6 年 前 0条评论

0
刘承志
刘承志
中级光能
中级光能

这道题涉及到有关二叉树的知识了，所以建议你把基础打牢再做，否则做起来很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲很费劲（*10000000000000000000000000000000000000）

阅读更多
举报

4 年，8 月 前 0条评论

0
0
徐润扬
徐润扬
高级守护
高级守护

这道题非常难，建议先打牢基础

阅读更多
举报

4 年，8 月 前 0条评论

0
0
刘乐宸
刘乐宸
新手天翼
新手天翼 
#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;
}

王兄，你看，这个贴那么久都没人，我趁乱发个整段代码没事吧！（发伪代码怕你看不懂，这个也是我抄的，哈哈），别举报，求采纳！

阅读更多
举报

4 年，4 月 前 8条评论

0
王泽宇
王泽宇
初级光能
初级光能

还可以，有方法做

王泽宇在2020-07-20 11:50:11追加了内容

查360

阅读更多
举报

4 年，4 月 前 0条评论

0
赵逸凡
赵逸凡
初级启示者
初级启示者

无论你是基础班还是提高班，建议你不要做

阅读更多
举报

6 年 前 5条评论

0
0
李显晨
李显晨
中级启示者
中级启示者

有这题吗？？？我为啥没搜到

阅读更多
举报

4 年 前 0条评论

0
0
张天璨
张天璨
新手天翼
新手天翼

我们的这个贴出名了！

 

阅读更多
举报

4 年，3 月 前 1条评论

0
0
刘乐宸
刘乐宸
新手天翼
新手天翼

难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 难 

阅读更多
举报

6 年 前 2条评论

0
栾峻岩
栾峻岩
初级天翼
初级天翼

这道题非常难，建议先打牢基础，这道题在酷町堂不是一般人能做出来的！（陆大神也不一定）

阅读更多
举报

6 年 前 2条评论

0
0
郑凝溪
郑凝溪
初级光能
初级光能

太难了，先打好基础，不要只想刷题！

阅读更多
举报

6 年 前 0条评论

0
崔乔昕
崔乔昕
中级光能
中级光能

难的话问老师不就行了？？？？？？？

阅读更多
举报

2 年，1 月 前 0条评论

0
柯以成
柯以成
新手光能
新手光能

这道题非常难，建议先打牢基础在做

阅读更多
举报

4 年，3 月 前 0条评论

0
0
0
李锦昊
李锦昊
中级天翼
中级天翼

李锦昊

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

 

阅读更多
举报

4 年，3 月 前 0条评论

0
0
张天璨
张天璨
新手天翼
新手天翼

你搜网上，网上可能有。 

张天璨在2020-08-04 09:45:51追加了内容

我们的这个贴出名了！

张天璨在2020-08-04 09:46:58追加了内容

酷町堂首页网址

阅读更多
举报

4 年，3 月 前 0条评论

0
丁振轩
丁振轩
资深光能
资深光能

难！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

阅读更多
举报

6 年 前 0条评论

0
陈喆鹏
陈喆鹏
资深光能
资深光能 
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a+b;
} 
陈喆鹏在2018-10-18 20:14:04追加了内容

看成1976了

阅读更多
举报

6 年，1 月 前 1条评论

0
0
杜文博
杜文博
资深守护
资深守护

  1. void adde(int a,int b,int c)

  2. {

  3. to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;cd[cnt]=c;

  4. to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;cd[cnt]=c;

  5. }

  6. #define LL long long

  7. int cir[N],D[N],fa[N],dep[N];

  8. bool vis[N];

  9. void findcir(int u)

  10. {

  11. dep[u]=dep[fa[u]]+1;

  12. int v,p;

  13. for(p=fir[u];p;p=nxt[p]){

  14. v=to[p];

  15. if(v==fa[u]) continue;

  16. if(!dep[v]){fa[v]=u;findcir(v);}

  17. else if(dep[v]<dep[u]){

  18. for(int j=u;;j=fa[j]){

  19. vis[j]=1;cir[++m]=j;

  20. if(j==v)break;

  21. }

  22. }

  23. }

  24. }

  25. LL hei[N],ans;

  26. void dfs(int u)

  27. {

  28. int v,p,w;

  29. for(p=fir[u];p;p=nxt[p]){

  30. v=to[p];w=cd[p];

  31. if(v!=fa[u]&&!vis[v]){

  32. dfs(v);

  33. ans=max(hei[u]+hei[v]+w,ans);

  34. hei[u]=max(hei[u],hei[v]+w);

  35. }

  36. }

  37. }

  38. LL g1[N],g2[N],h1[N],h2[N];

  39. int main()

  40. {

  41. int n,i,u,v,w,p;

  42. scanf("%d",&n);

  43. for(i=1;i<=n;i++){

  44. scanf("%d%d%d",&u,&v,&w);

  45. adde(u,v,w);

  46. }

  47. findcir(1);

  48. for(i=1;i<=n;i++)

  49. if(vis[i]) dfs(i);

  50. cir[m+1]=cir[1];

  51. for(i=1;i<=m;i++)

  52. for(p=fir[cir[i]];p;p=nxt[p])

  53. if(to[p]==cir[i+1]){

  54. D[i]=cd[p];

  55. break;

  56. }

  57. LL sum=0,mx=hei[cir[1]]+D[1];

  58. for(i=2;i<=m;i++){

  59. sum+=D[i-1];

  60. h1[i]=max(h1[i-1],hei[cir[i]]+sum);

  61. g1[i]=max(g1[i-1],hei[cir[i]]+mx);

  62. mx=max(mx,hei[cir[i]])+D[i];

  63. }

  64. sum=0;mx=hei[cir[1]]+D[m];

  65. for(i=m;i>1;i--){

  66. sum+=D[i];

  67. h2[i]=max(h2[i+1],hei[cir[i]]+sum);

  68. g2[i]=max(g2[i+1],hei[cir[i]]+mx);

  69. mx=max(mx,hei[cir[i]])+D[i-1];

  70. }

  71. LL ret=1ll<<60;

  72. for(i=1;i<=m;i++)

  73. ret=min(ret,max(ans,max(h1[i]+h2[i+1],max(g1[i],g2[i+1]))));

  74. printf("%.1f",1.0*ret/2);

  75.  

 

阅读更多
举报

4 年，1 月 前 1条评论

0
0
0
0
0
荣光峰
荣光峰
资深光能
资深光能

先打好基础，这题太难了。

阅读更多
举报

4 年，3 月 前 0条评论

0
0
刘英杰
刘英杰
新手天翼
新手天翼

这道题有一个简单思路，就是贪心……（不用谢我，叫我雷锋）

阅读更多
举报

4 年，6 月 前 0条评论

0
刘英杰
刘英杰
新手天翼
新手天翼

这道题有一个简单思路，就是贪心……（不用谢我，叫我雷锋）

阅读更多
举报

4 年，6 月 前 0条评论

0
0
0
0
0
0
0
被禁言 刘宇航
刘宇航
修练者
修练者

                                       难！                  难！

                                   难！难！         难！难！难！

难！ 难！ 难！           难！ 难！                难！

   难！  难！           难！    难！           难！难！难！

        难！                          难！                 难！

   难！     难！                   难！           难！难！难！

                                         难！                  难！

                                         难！           难！难！难！

阅读更多
举报

3 年，5 月 前 0条评论

我要回答
© 2021 酷町堂教育机构 版权所有 皖ICP备16015773号-1