题解与讨论区 1192: dzerzhinski 的王国

题解与讨论区 1192: dzerzhinski 的王国

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB

返回问题页面

题目描述

dzerzhinski 终于有一天成立了自己的acm王国,但与此同时他被一件事愁坏了(没有什么事情能难倒dzerzhinski,他只是假装愁坏了,因为这样才能考你),于是他来求助你。 

在dzerzhinski的王国里面有N个区域,不同区域间通过M条道路连接,道路是双向的,每条道路有着相应的长度Si。王国有一个首都,首都的编号为1,存在着K条特殊的道路能够直接从首都前往到另一个区域,这类道路各自也有对应的长度yi,我们把这类道路称为快速转移道路。保证首都能够通过道路直接或者间接到达任意区域。  

dzerzhinski想拆掉一些快速转移道路,他想知道最多可以同时移除多少条快速转移导读使得从中心区域到任意区域的最短长度不变。 



第1192题的题解