景点中心
测试数据来自 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届中小学生计算机程序设计竞赛决赛试题(高中组)第四题