青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219411
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜


Always On the Run

Time limit: 1 Seconds?? Memory limit: 32768K??
Total Submit: 125?? Accepted Submit: 70??

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 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 numbered 1, 2, ..., n, where 1 is Paris, her starting point, and n is Atlanta, her final destination. The numbers will satisfy 2 <= n <= 10 and 1 <= k <= 1000.
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 (2, 3, ..., n), the next n - 1 lines to those from city 2 to all others (1, 3, 4, ..., n), and so on.

The description of the flight schedule itself starts with an integer d, the length of the period in days, with 1 <= d <= 30. Following this are d non-negative integers, representing the cost of the flight between the two cities on days 1, 2, ..., d. A cost of 0 means that there is no flight between the two cities on that day.

So, for example, the flight schedule ``3 75 0 80'' means that on the first day the flight costs 75, on the second day there is no flight, on the third day it costs 80, and then the cycle repeats: on the fourth day the flight costs 75, there is no flight on the fifth day, etc.

The input is terminated by a scenario having n = k = 0.


Output

For each scenario in the input, first output the number of the scenario, as shown in the sample output. If it is possible for Trisha to travel k days, starting in city 1, each day flying to a different city than the day before, and finally (after k days) arriving in city n, then print ``The best flight costs x.'', where x is the least amount that the k flights can cost.

If it is not possible to travel in such a way, print ``No flight possible.''.

Print a blank line after each scenario.


Sample Input

3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0


Sample Output

Scenario #1
The best flight costs 460.

Scenario #2
No flight possible.

#include?<iostream>
using?namespace?std;

const?int?MAXN?=?11;
const?int?MAXM?=?1001;
const?int?INF?=??2000000000;

int?n,?m;
int?a[MAXN][MAXN][MAXM];
int?d[MAXM][MAXN];
int?num[MAXN][MAXN];

int?main()
{
????
int?i,?j,?k,?l;
????
int?t,?t1;
????
int?tmp?=?0;
????
while?(scanf("%d%d",?&n,?&m)?!=?EOF)?{
????????
if?(n?==?0?&&?m?==?0)?break;
????????memset(a,?
0,?sizeof(a));
????????
for?(i=1;?i<=n;?i++)?{
????????????
for?(j=1;?j<=n;?j++)?{
????????????????
if?(i?!=?j)?{
????????????????????scanf(
"%d",?&num[i][j]);
????????????????????
for?(k=1;?k<=num[i][j];?k++)?{
????????????????????????scanf(
"%d",?&a[i][j][k]);
????????????????????}

????????????????}

????????????}

????????}

????????
for?(i=1;?i<=m;?i++)?{
????????????
for?(j=1;?j<=n;?j++)?{
????????????????d[i][j]?
=?INF;
????????????}

????????}

????????
for?(j=1;?j<=n;?j++)?{
????????????
if?(a[1][j][1]?>?0)?{
????????????????d[
1][j]?=?a[1][j][1];
????????????}

????????}

????????
for?(i=2;?i<=m;?i++)?{
????????????
for?(j=1;?j<=n;?j++)?{
????????????????t?
=?INF;
????????????????
for?(k=1;?k<=n;?k++)?{
????????????????????
if?(k?==?j)?continue;
????????????????????t1?
=?i?%?num[k][j]?>?0???i?%?num[k][j]?:?num[k][j];
????????????????????
if?(a[k][j][t1]?>?0?&&?t?>?d[i-1][k]?+?a[k][j][t1])?{
????????????????????????t?
=?d[i-1][k]?+?a[k][j][t1];
????????????????????}

????????????????}

????????????????d[i][j]?
=?t;
????????????}

????????}

????????printf(
"Scenario?#%d\n",?++tmp);
????????
if?(d[m][n]?!=?INF)?{
????????????printf(
"The?best?flight?costs?%d.\n\n",?d[m][n]);
????????}
?else?{
????????????printf(
"No?flight?possible.\n\n");
????????}

????}

????system(
"pause");
????
return?0;
}

posted on 2006-10-12 00:41 閱讀(577) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久精品欧美日韩| 亚洲欧美国产视频| 国模叶桐国产精品一区| 亚洲日韩欧美一区二区在线| 国产精品一区二区三区四区五区| 亚洲日产国产精品| 亚洲国产日韩欧美在线动漫| 久久高清免费观看| 欧美伊人久久大香线蕉综合69| 欧美日韩国产一区| 亚洲国产女人aaa毛片在线| 激情综合五月天| 欧美一区二视频| 久久国产精品99久久久久久老狼| 欧美日韩一卡二卡| 激情欧美一区二区| 欧美亚洲系列| 久久精品国产一区二区三区| 欧美一区二区成人6969| 欧美在线首页| 国产曰批免费观看久久久| 午夜精品久久久久久久白皮肤| 亚洲一级二级| 国产精品美女久久久| 亚洲影视在线| 久久99伊人| 好吊一区二区三区| 久久先锋影音av| 欧美国产专区| 一本色道久久88综合日韩精品| 欧美精品久久久久久| 亚洲精品中文字| 亚洲欧美国产毛片在线| 国产精品久久久久aaaa| 香蕉成人伊视频在线观看| 久久精品免费播放| 亚洲国产99| 欧美国产日本韩| 一区二区欧美日韩| 欧美一级电影久久| 国产一区二区毛片| 欧美成人精品影院| 一本一道久久综合狠狠老精东影业 | 日韩视频在线观看一区二区| 欧美激情在线观看| 中文精品99久久国产香蕉| 新67194成人永久网站| 国外精品视频| 欧美激情综合色综合啪啪| 99精品国产热久久91蜜凸| 欧美一区二区三区视频在线| 揄拍成人国产精品视频| 欧美金8天国| 亚洲欧美日韩另类| 欧美黄色一级视频| 午夜欧美大尺度福利影院在线看| 国产综合精品一区| 欧美剧在线免费观看网站| 亚洲一区二区高清视频| 嫩草国产精品入口| 亚洲尤物视频网| 亚洲电影av在线| 国产精品久久久久久亚洲调教| 久久久999精品免费| 99这里有精品| 免费欧美电影| 西西裸体人体做爰大胆久久久| 亚洲大胆美女视频| 国产精品天天看| 欧美精品大片| 久久久久国产精品午夜一区| 日韩一级大片| 欧美第一黄网免费网站| 欧美一级久久久| 99精品欧美一区| 在线免费观看一区二区三区| 国产精品久久久999| 欧美激情视频免费观看| 久久久久9999亚洲精品| 亚洲线精品一区二区三区八戒| 欧美高清视频一二三区| 久久精品在线播放| 午夜伦欧美伦电影理论片| 一本大道久久a久久综合婷婷| 精品电影在线观看| 国产亚洲精品美女| 国产精品无码永久免费888| 欧美片网站免费| 欧美暴力喷水在线| 久久人体大胆视频| 久久精品人人做人人综合| 亚洲欧美一区二区视频| 一本色道婷婷久久欧美| 亚洲精品在线一区二区| 91久久精品国产91性色| 欧美成人高清视频| 美女网站在线免费欧美精品| 久久久噜噜噜久久中文字免 | 日韩一级免费观看| 亚洲黄色免费网站| 最新中文字幕一区二区三区| 伊人伊人伊人久久| 伊人夜夜躁av伊人久久| 在线观看欧美日本| 在线观看视频欧美| 亚洲高清免费在线| 在线看片成人| 亚洲精品1区2区| 亚洲精品一级| 一区二区三区www| 亚洲视频观看| 性久久久久久| 久久男人资源视频| 欧美va天堂| 亚洲国产精品va| 亚洲精品国产欧美| 一区二区三区www| 亚洲欧美成人| 久久久噜噜噜久久人人看| 麻豆九一精品爱看视频在线观看免费 | 亚洲免费一级电影| 午夜一区二区三视频在线观看| 午夜欧美大尺度福利影院在线看| 欧美亚洲在线观看| 久久视频在线视频| 欧美精品日韩精品| 国产精品老牛| 激情五月综合色婷婷一区二区| 亚洲第一天堂无码专区| 一区二区三区蜜桃网| 午夜日韩av| 美国成人直播| 日韩午夜免费视频| 性久久久久久久久| 久久久噜噜噜久久| 欧美日韩亚洲国产精品| 国产日韩欧美麻豆| 亚洲精品国产精品国自产观看 | 午夜一区二区三区不卡视频| 久久亚洲免费| 一本色道久久综合一区| 欧美一级片久久久久久久| 欧美jizzhd精品欧美喷水| 欧美性生交xxxxx久久久| 国产真实精品久久二三区| 日韩视频在线观看| 久久久夜色精品亚洲| 最近中文字幕mv在线一区二区三区四区| 亚洲视频免费| 欧美黑人在线播放| 国产午夜精品久久| 在线综合亚洲欧美在线视频| 久久婷婷国产综合国色天香| 日韩午夜在线| 免费不卡亚洲欧美| 国产一区香蕉久久| 亚洲一区制服诱惑| 欧美激情1区2区| 香蕉久久夜色精品国产| 欧美日韩三区四区| 136国产福利精品导航网址| 亚洲资源av| 亚洲精品黄网在线观看| 久久久亚洲精品一区二区三区| 国产精品hd| 99视频精品在线| 欧美激情在线免费观看| 久久成人免费| 国产欧美日韩| 亚洲制服av| 亚洲日本成人女熟在线观看| 久久午夜精品| 一区三区视频| 久久久xxx| 午夜影视日本亚洲欧洲精品| 国产精品高潮呻吟久久av黑人| 亚洲精品中文字幕在线| 欧美.日韩.国产.一区.二区| 久久成人av少妇免费| 国产日韩一区欧美| 欧美一区视频| 亚洲欧美精品在线| 国产欧美精品一区二区三区介绍| 亚洲一级二级在线| 一区二区三区日韩欧美| 欧美肉体xxxx裸体137大胆| 一区二区三区精品国产| 日韩视频在线一区二区三区| 欧美日韩成人精品| 亚洲视频狠狠| 一本高清dvd不卡在线观看| 欧美日韩一区二区三区高清| 一区二区三区四区蜜桃| 日韩一区二区免费高清| 欧美午夜一区| 亚洲欧美中文日韩v在线观看| 亚洲午夜影视影院在线观看| 国产精品自拍三区| 久久久青草青青国产亚洲免观| 久久精品一区二区三区不卡|