P3094 [USACO13DEC]假期计划Vacation Planning

    • 186通过
    • 543提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2013
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有N(1 <= N <= 200)个农场,用1..N编号。航空公司计划在农场间建立航线。对于任意一条航线,选择农场1..K中的农场作为枢纽(1 <= K <= 100, K <= N)。

    当前共有M (1 <= M <= 10,000)条单向航线连接这些农场,从农场u_i 到农场 v_i, 将花费 d_i美元。(1 <= d_i <= 1,000,000).

    航空公司最近收到Q (1 <= Q <= 10,000)个单向航行请求。第i个航行请求是从农场a_i到农场 b_i,航行必须经过至少一个枢纽农场(可以是起点或者终点农场),因此可能会多次经过某些农场。

    请计算可行航行请求的数量,及完成所有可行请求的总费用。

    输入输出格式

    输入格式:

    * Line 1: Four integers: N, M, K, and Q.

    * Lines 2..1+M: Line i+1 contains u_i, v_i, and d_i for flight i.

    * Lines 2+M..1+M+Q: Line 1+M+i describes the ith trip in terms of a_i and b_i

    输出格式:

    * Line 1: The number of trips (out of Q) for which a valid route is possible.

    * Line 2: The sum, over all trips for which a valid route is possible, of the minimum possible route cost.

    输入输出样例

    输入样例#1: 复制
    3 3 1 3 
    3 1 10 
    1 3 10 
    1 2 7 
    3 2 
    2 3 
    1 2 
    
    输出样例#1: 复制
    2 
    24 
    

    说明

    There are three farms (numbered 1..3); farm 1 is a hub. There is a $10 flight from farm 3 to farm 1, and so on. We wish to look for trips from farm 3 to farm 2, from 2->3, and from 1->2.

    The trip from 3->2 has only one possible route, of cost 10+7. The trip from 2->3 has no valid route, since there is no flight leaving farm 2. The trip from 1->2 has only one valid route again, of cost 7.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。