Problem 1434 --单身晚会1434: 单身晚会
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$195$ |
正确数量 |
$51$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
图论 |
当前分类(单击移除)：
图论
单击选择分类：
ZJ和ZCX在一起很久了，两个人都互生爱意，最终决定喜结良缘，从此踏入浪漫的婚姻殿堂。
但是，ZJ的好基友们想到以后ZJ就不能经常跟他们一起愉快的玩耍了，都觉得非常伤心难过，于是他们决定在最后一晚为ZJ开一场单身晚会，玩整晚紧张刺激的飞行棋。
ZJ的好基友居住在城市的各个地方（每个地方不一定只有一个基友），他们需要从各个地方赶到其中一个朋友的家里来参加这最后的单身PARTY，ZJ被基友们的热情深深感动了，决定对基友们来时的路费进行报销。报销规则按照距离来计算。基友们为了帮ZJ省钱，决定在所有人走最短路径的情况下，总距离最小的人的家里开PARTY。
ZJ想知道基友们走过的总距离是多少，然后他把总共需要报销的钱拿出来，就可以让基友们自己来分配了。但是他算了半天也没算出来总距离是多少，单身PARTY马上就开始了，你能帮帮他吗？
第一行一个整数T，表示有T（T<15）组数据
每组数据的第一行基友数（包括ZJ）N（N<100），路口P（2<=P<=100）,路口之间道路数C(1<=C<=1450)，（基友的编号为1…N，路口的编号为1…P）
第二行到第N+1行：编号为1到N的基友们家所在的路口号。
第N+2行到N+C+1行：每行有三个数：相连的路口A,B，路口间间距D（1<=D<=255），当然，连接是双向的。
每组数据输出占一行，输出大家必须要走的最小距离和
1
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
经测试，本题数据和题意不符合，现对题意做如下修正：
选择一个路口（不一定要有人住），使所有人到这个路口的路程和最小化
这题应该是省赛现场修改题意，但这里用的是原题意，特此说明。对被卡的同学再次表示歉意。对其他题目有疑义的可以联系管理员。
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$45 $ms]
|
找队友，能刷题的那种
|
414188
|
2019-05-03 10:38:22 |
| 内存最少[$1280 $KB]
|
alaso2018
|
423532 |
2019-05-10 23:35:46 |
| 第一AC |
AOJ大管家 |
46665
|
2017-01-26 11:58:40 |
| 第一挑战 |
AOJ大管家
|
46665 |
2017-01-26 11:58:40 |
| 竞赛编号 |
竞赛名称 |
竞赛时间 |
访问比赛 |
| 1647 |
安科ACM集训队-2021（3）图论专题 |
2021-05-03 10:00:00 |
请登录
|
| 1504 |
2020图灵NOIP冬令营 day5 |
2020-01-17 08:00:00 |
请登录
|
| 1334 |
图灵2019五一高级算法集训营：图论专题 |
2019-05-03 09:30:00 |
请登录
|