Problem #1: 选地址(adress)
Description
小X有很多朋友、、分布在N个城市。。
这N个城市之间,有些有直接的道路,有些是间接联通的(保证任何两个城市都可以相互到达。。)
但是、经过每条道路都是有代价的、、
于是。。
小X希望你来帮他找出一个城市,使得他的所有朋友到这个城市的代价最小。
【Input Format】
输入共2* n+1行,
其中第一行为一个整数N、
第2~N+1行
每行有N个整数、表示两个城市间的代价、(0表示不直接连通)
第n+2~2* N+1行
每行一个整数。表示每个城市中小X的朋友数。
【Output Format】
输出有两行。
第一行为你选中的城市
第二行为最小需要的代价。
Sample 1
Input
5
0 1 2 0 0
1 0 0 0 20
2 0 0 10 0
0 0 10 0 1
0 20 0 1 0
2
3
4
5
6
Output
4
109
Limitation
1s, 128MiB for each test case.
Data Limit
对于100%的数据,n<=200,输出保证不超过longint
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者