2516: 科比中国行
题目描述
奥运会正在如火如荼地进行中,美国篮球巨星科比布莱恩特随队出征奥运,但他却
遇到了一个麻烦——8 月份的“科比中国行”的路线还没有确定,由于奥运赛程密集,
科比没有时间去亲自完成路线制定,他便想到了自己的好朋友——欢总,科比在电话中
于欢总说明了情况,欢总也爽快地答应帮科比这个忙,所要解决的问题如下:
科比指定了 n 个最喜欢的城市(分别用 1......n,n 个正整数表示),每个城市都有
数量巨大的活动供他参加,他每天只能参加一个城市的一个活动,并且连续两天不能待
在同一个城市(即每天均会乘坐私人飞机到达另一个城市)。 科比的“中国行”天数为
k + 1 天,并且指定了活动开始的城市和活动结束的城市,由于他要在中国待 k + 1 天,
也就意味着他会有 k 次航班安排,坐飞机是一件很累的事情,所以科比希望能为他制定
一条满足要求的并且 k 次航班加起来的里程数最小的一条路线。并且科比想要知道如果
他每次都按照这个路线行动的话,他最多能进行多少次“中国行”活动使他的航班的总
里程数不超过一个他心目中的值。
但是很不幸,欢总在传家宝分配上出了问题,他的多名女朋友扬言要杀了他,他只
好暂时逃到了阿富汗,在他走之前他留下了一张纸条说道“希望夏令营的小朋友们能为
他做这个事情,等他回来后定有重赏”。
输入
第一行是 5 个用空格隔开的正整数:n, s, t, k, sum。分别表示城市的数量 n、活
动开始的城市 s、活动结束的城市 t、航班次数 k、科比心目中的总里程数 sum。
接下来会有 n 行,每行 n 个用空格隔开的正整数,即 n 个城市两两之间的距离(均
小于 1000),-1 代表两个城市之间无法通行。
输出
输出一行:若不可能通过 k 次航班从 s 到达 t,则直接输出-1;否则输出两个整数:
最小的 k 次航班的里程数之和、为使总里程数不超过 sum 最多进行的“中国行”次数(取
整数部分),两个整数之间用一个空格隔开。
样例输入 复制
4 2 1 2 55
-1 11 4 8
11 -1 6 2
4 6 -1 3
8 2 3 -1样例输出 复制
10 5提示
为通过两次航班从 2 -> 1, 可发现 2 -> 3 -> 1 路线使得里程和最小,为 10;由
于 sum 为 55,所以需要进行的 “中国行”的次数为 55 / 10 = 5 次。
50%
0<n<=100, 0<k<=50, 0<sum<10^6;
80%
0<n<=100, 0<k<=10^6, 0<sum<10^9;
100%
0<n<=100, 0<k<=10^6, 0<sum<10^100。