有编号从 开始的 个房间,有一只老鼠将会出现在某个房间中
当老鼠在某一时刻位于房间 时,它将在下一时刻抵达房间 (如果 则代表老鼠不会离开 房间)
已知在第 个房间布置捕鼠夹的价格是 ,求最少需要花费多少能够使得无论老鼠从哪个房间出现,都会抵达有老鼠夹的房间。
第一行输入一个整数
第二行输入 个整数 为在第 个房间布置捕鼠夹的成本
第三行输入 个整数 为在 房间的老鼠即将抵达的房间编号
输出一个整数,为满足条件的最小花费
5
1 2 3 2 10
1 3 4 3 3
3
4
1 10 2 10
2 4 2 2
10
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
2
在第一组样例里可以选择房间1
和房间4
布置捕鼠夹。如果老鼠从房间1
出现,则会被房间1
的捕鼠夹捕获,否则会被房间4
的捕鼠夹捕获。
在第二组样例里可以在房间2
布置捕鼠夹,老鼠从任意房间出现,都会被房间2
的捕鼠夹捕获。
这是第三组样例中老鼠可能的行动轨迹:
1→2→2→…;
2→2→…;
3→2→2→…;
4→3→2→2→…;
5→6→7→6→…;
6→7→6→…;
7→6→7→…;
所以可以在房间2
和房间6
布置捕鼠夹