Skip to content

12207: 【原2207】科比中国行

题目

题目描述

author: 廖予科 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2207

Description

奥运会正在如火如荼地进行中,美国篮球巨星科比布莱恩特随队出征奥运,但他却遇到了一个麻烦——8月份的“科比中国行”的路线还没有确定,由于奥运赛程密集,科比没有时间去亲自完成路线制定,他便想到了自己的好朋友——欢总,科比在电话中于欢总说明了情况,欢总也爽快地答应帮科比这个忙,所要解决的问题如下:

科比指定了n个最喜欢的城市(分别用1……n,n个正整数表示),每个城市都有数量巨大的活动供他参加,他每天只能参加一个城市的一个活动,并且连续两天不能待在同一个城市(即每天均会乘坐私人飞机到达另一个城市)。科比的“中国行”天数为k + 1天,并且指定了活动开始的城市和活动结束的城市,由于他要在中国待k + 1天,也就意味着他会有k次航班安排,坐飞机是一件很累的事情,所以科比希望能为他制定一条满足要求的并且k次航班加起来的里程数最小的一条路线。并且科比想要知道如果他每次都按照这个路线行动的话,他需要多少次“中国行”活动才能使他的航班的总里程数达到一个他心目中的值。

但是很不幸,欢总在传家宝分配上出了问题,他的多名女朋友扬言要杀了他,他只好暂时逃到了阿富汗,在他走之前他留下了一张纸条说道“希望11级ACM班的同学们能为他做这个事情,等他回来后定有重赏”。

Input Format

第一行是5个用空格隔开的正整数:n, s, t, k, sum。分别表示城市的数量n、活动开始的城市s、活动结束的城市t、航班次数k、科比心目中的总里程数sum。

接下来会有n行,每行n个用空格隔开的正整数,即n个城市两两之间的距离(均小于1000),-1代表两个城市之间无法通行。

Output Format

输出一行: 若不可能通过k次航班从s到达t,则直接输出-1. 否则输出两个整数:最小的k次航班的里程数之和、为使总里程数达到sum所需的“中国行”次数(取整数部分),两整数用空格隔开。

Hint

1、不考虑飞机的飞行时间
2、可多次待在同一个城市(但不能在连续的两天)
3、两个城市之间的距离要不是正整数要不是-1(-1代表不能通行).

Sample Input

4 2 1 2 55    
-1 11 4 8     
11 -1 6 2     
4 6 -1 3     
8 2 3 -1

Sample Output

10 5

explaination:为通过两次航班从2 -> 1, 可发现2 -> 3 -> 1路线使得里程和最小,为10;由于sum为55,所以需要进行的  “中国行”的次数为55 / 10 = 5次。

Data Scale

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

Oops! 本题目还没有解答!

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

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

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