Skip to content

14133: 【原4133】Psycho Pass

题目

题目描述

author: 黄俊翔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4133 ## Description

为了掩盖进攻厚生省诺那塔的真实意图,槙岛圣护在城市中安插了大量头盔党,并指使他们于指定的时间地点发起指定时长的恐怖袭击。所幸的是狡啮慎也在攻击开始前找到了槙岛的计划表,并将其交给了公安局长禾生壤宗。局长观察了一下,城市可以抽象成地点和双向道路,道路的距离已经抽象为了时长(双向时长也相等)。一开始警察们可以分成几队,提前到某些地点待命。由于不知道头盔党的藏身处,警察们只能等待恐怖袭击开始并进行防守,直到槙岛指定的时长已经过去了,头盔党就会撤退,这一队警察才能赶往下一个地点待命。此外,槙岛是按小队安排头盔党,可能存在某个时刻上同一个地点有多队头盔党发起进攻,此时必须有同样多队的警察才能守住。

由于以希比拉系统为社会和平的基础,公安局的警力早就大幅缩减,因此公安局几乎不可能派出和头盔党同样多队数的警察,只能让警察们在防守完一次袭击之后火速赶去下一个预订的袭击地点来节省警力。禾生局长想要知道,要防守住所有的恐怖袭击,最少需要多少队警察。

Output Format

有T组输出,对应T组输入。

每组数据的第一行为两个正整数N,M,表示城市有N个地点,头盔党总共有M队。

接下来一个N*N的自然数和-1组成的邻接矩阵,表示地点之间相互抵达所需的时长。矩阵的对角线必然为0,不可抵达以-1表示,其他位置都为正整数,且矩阵为对称矩阵。

接下来M行,每行三个正整数a,b,c,表示有一队头盔党将会于b时刻在a地点发起时长为c的恐怖袭击。

Sample Input

1
3 4
0 2 1
2 0 3
1 3 0
1 3 5
2 3 5
3 9 3
3 9 4

Sample Output

2

数据解释:因为地点1的警察完成防守之后,可以赶往地点3防守下一波恐怖袭击,时间刚刚好。但地点2的警察们由于去地点3的距离太远来不及过去,而地点3在时刻9时需要2队警察防守,所以总共需要3队警察。

Data Range

对于\(50\%\)的数据,\(N \le 5, M \le 10\)。

对于\(100\%\)的数据,\(T \le 5, N \le 50, M \le 1000\),其他所有数值\(\le 100000\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!