景点中心

景点中心

测试数据来自 system/1487

描述

话说宁波市的中小学生在镇海中学参加计算机程序设计比赛,比赛之余,他们在镇海中学的各个景点参观。镇海中学共有n个景点,每个景点均有若干学生正在参观。这n个景点以自然数1至n编号,每两个景点的编号均不同。每两个景点之间有且只有一条路径。选择哪个景点集中所有的学生,才能使所有学生走过的路径之和最小呢?

格式

输入格式

第一行只有一个正整数n,表示景点数。

第二行有n个1至1000间的整数,这n个整数间互相以一个空格分隔。其中第i个整数表示第i个景点处的学生数。

第三行至第n+1,每行有三个整数i,j,k,表示景点i和景点j之间有一条长为k的路径直接连接。其中i<>j,1≤i≤n, 1≤j≤n;1≤k≤1000。

输出格式

有二行:
第一行只有一个整数i,表示在第i个景点处集中时,所有学生走过的路径之和最短。

第二行也只有一个整数,表示所有学生走过的路径之和的最小值。

样例1

样例输入1

4
3 2 4 1
1 2 5
3 1 6
2 4 4

样例输出1

1
43

限制

1s

提示

【样例说明】
如上图所示,景点1有3个学生,景点2有2个学生,景点3有4个学生,景点4有1个学生;景点1与景点2间距离5,景点1与景点3间距离6,景点2与景点4间距离4。此时,选择在景点1处集中时,所有学生走过的路径之和为最小,该最小值为43。

【数据限制】
所有的数据均随机生成,且满足:
30%的数据,1≤n≤200。

60%的数据,1≤n≤3000。

100%的数据,1≤n≤100000。

来源

宁波市第23届中小学生计算机程序设计竞赛决赛试题(高中组)第四题

信息

ID
1579
难度
(无)
分类
动态规划 | 树形DP 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者