·天新网首页·加入收藏·设为首页·网站导航
数码笔记本手机摄像机相机MP3MP4GPS
硬件台式机网络服务器主板CPU硬盘显卡
办公投影打印传真
家电电视影院空调
游戏网游单机动漫
汽车新车购车试驾
下载驱动源码
学院开发设计
考试公务员高考考研
业界互联网通信探索
您现在的位置:天新网 > 软件开发
UVA 590 Always on the run(dp)
http://www.21tx.com 2014年01月20日 CSDN 帆帆帆帆帆帆帆帆帆帆

1 2 下一页

Screeching tires. Searching lights. Wailing sirens. Police cars everywhere. Trisha Quickfinger did it again! Stealing the `Mona Lisa' had been more difficult than planned, but being the world's best art thief means expecting the unexpected. So here she is, the wrapped frame tucked firmly under her arm, running to catch the northbound metro to Charles-de-Gaulle airport.

But even more important than actually stealing the painting is to shake off the police that will soon be following her. Trisha's plan is simple: for several days she will be flying from one city to another, making one flight per day. When she is reasonably sure that the police has lost her trail, she will fly to Atlanta and meet her `customer' (known only as Mr. P.) to deliver the painting.

Her plan is complicated by the fact that nowadays, even when you are stealing expensive art, you have to watch your spending budget. Trisha therefore wants to spend the least money possible on her escape flights. This is not easy, since airlines prices and flight availability vary from day to day. The price and availability of an airline connection depends on the two cities involved and the day of travel. Every pair of cities has a `flight schedule' which repeats every few days. The length of the period may be different for each pair of cities and for each direction.

Although Trisha is a good at stealing paintings, she easily gets confused when booking airline flights. This is where you come in.

Input

The input file contains the descriptions of several scenarios in which Trisha tries to escape. Every description starts with a line containing two integers n and k. n is the number of cities through which Trisha's escape may take her, and k is the number of flights she will take. The cities are numberedUVA 590 Always on the run(dp), where 1 is Paris, her starting point, and n is Atlanta, her final destination. The numbers will satisfy UVA 590 Always on the run(dp) and UVA 590 Always on the run(dp).

Next you are given n(n - 1) flight schedules, one per line, describing the connection between every possible pair of cities. The first n - 1 flight schedules correspond to the flights from city 1 to all other cities (UVA 590 Always on the run(dp)), the next n - 1 lines to those from city 2 to all others ( UVA 590 Always on the run(dp)), and so on.

The description of the flight schedule itself starts with an integer d, the length of the period in days, with UVA 590 Always on the run(dp). Following this are d non-negative integers, representing the cost of the flight between the two cities on days UVA 590 Always on the run(dp). A cost of 0 means that there is no flight between the two cities on that day.

上一篇: 使用适用于 WinJS 应用程序的 CSS 构建响应迅速的现代 UI
下一篇: 领域驱动设计的编码:数据聚焦型开发的技巧 - 第 3 部分

1 2 下一页

关于我们 | 联系我们 | 加入我们 | 广告服务 | 投诉意见 | 网站导航
Copyright © 2000-2011 21tx.com, All Rights Reserved.
晨新科技 版权所有 Created by TXSite.net