| 比赛场次 | 755 |
|---|---|
| 比赛名称 | 26暑假集训模拟赛3 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2026-07-06 08:00:00 |
| 结束时间 | 2026-07-06 13:00:00 |
| 开放分组 | 全部用户 |
| 组织者 | HXF |
| 注释介绍 |
| 题目名称 | 城市建设 |
|---|---|
| 输入输出 | hnoi2010_city.in/out |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 162 MiB |
| 测试点数 | 20 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 zcx |
AAAAAAAAAAAAATTTTTTA |
35.822 s | 4.28 MiB | 70 |
 王潇翊 |
AAAAAAAAAAAEEEEEEEEA |
5.333 s | 3.61 MiB | 60 |
|
RpUtl |
AAAAAAAAAAAWWTTTTTTA |
34.159 s | 3.92 MiB | 60 |
|
ChenBp |
AAAAAAAAAAATTTTTTTTA |
42.356 s | 3.95 MiB | 60 |
|
dream |
AAAAAAAAAAATTTTTTTTA |
42.487 s | 3.99 MiB | 60 |
|
Lixj |
AAAAAAAAAAATTTTTTTTA |
43.234 s | 3.87 MiB | 60 |
|
2_16鸡扒拌面 |
AAAAAAAAAAATTTTTTTTA |
43.889 s | 4.31 MiB | 60 |
|
梦那边的美好CE |
AAAAAAAAAAATTTTTTTTA |
43.906 s | 4.49 MiB | 60 |
 赵飞羽 |
AAAAAAAAAAATTTTTTTTA |
44.408 s | 4.18 MiB | 60 |
|
彭欣越 |
AAAAAAAAAAATTTTTTTTA |
45.139 s | 4.20 MiB | 60 |
|
rzzakioi |
AAAAAAAAAAATTTTTTTTA |
45.422 s | 5.17 MiB | 60 |
|
KKZH |
AAAAAAAAAAATTTTTTTTA |
46.202 s | 4.47 MiB | 60 |
|
VTXE |
AAAAAAAAAAATTTTTTTTA |
46.536 s | 4.48 MiB | 60 |
 exil |
AAAAAAAAAAATTTTTTTTA |
46.563 s | 4.48 MiB | 60 |
|
郑霁桓 |
AAAAAAAAAAATTTTTTTTA |
46.934 s | 9.24 MiB | 60 |
|
对立猫猫对立 |
AAAAAAAAAATTTTTTTTTW |
47.316 s | 3.92 MiB | 50 |
|
123 |
AAWWWWWWWWWTTTTTTTTW |
44.208 s | 4.04 MiB | 10 |
|
Ruyi |
AAWWWWWWWWTTTTTTTTTW |
47.867 s | 4.17 MiB | 10 |
|
PXCZM |
AWWWWWWWWWWWWTTTTTTW |
34.591 s | 3.96 MiB | 5 |
【题目描述】
$ PS $国是一个拥有诸多城市的大国，国王 Louis 为城市的交通建设可谓绞尽脑汁。 Louis 可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。 Louis 希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变， Louis 会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和， Louis 决定求助于你来完成这个任务。大样例
【输入格式】
文件第一行包含三个整数$ N , M , Q $，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。
接下来$ M $行，第$ i + 1 $行有三个用空格隔开的整数$ X_i , Y_i , Z_i ( 1 ≤ X_i , Y_i ≤ n , 0 ≤ Z_i ≤ 5×10^7) $，表示在城市Xi与城市Yi之间修建道路的代价为$ Z_i $。
接下来$ Q $行，每行包含两个数$ k , d $，表示输入的第$ k $个道路的修建代价修改为$ d $(即将$ Z_k $修改为$ d $)。
【输出格式】
输出包含$ Q $行，第$ i $行输出得知前$ i $条消息后使城市连通的最小花费总和。
【样例输入】
5 5 3 1 2 1 2 3 2 3 4 3 4 5 4 5 1 5 1 6 1 1 5 3
【样例输出】
14 10 9
【提示】
对于$ 20\% $的数据, $ n ≤ 1000, m ≤ 6000 , Q ≤ 6000 $。
有$ 20\% $的数据，$ n ≤ 1000 , m ≤ 50000 , Q ≤ 8000 $,修改后的代价不会比之前的代价低。
对于$ 100\% $的数据, $ n ≤ 20000 , m ≤ 50000 , Q≤50000 $。