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

隨筆 - 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>
            麻豆久久精品| 欧美第一黄色网| 国产视频自拍一区| 欧美怡红院视频一区二区三区| 亚洲最黄网站| 国产精品尤物| 毛片一区二区| 欧美日韩国产成人高清视频| 中日韩美女免费视频网址在线观看| 一本久久精品一区二区| 国产欧美另类| 亚洲国产另类久久精品| 欧美巨乳在线| 久久国产精品免费一区| 免费在线成人av| 亚洲一区二区三区免费视频| 午夜精品成人在线| 91久久国产精品91久久性色| 亚洲精品孕妇| 国产一区二区三区久久久| 亚洲国产成人porn| 国产精品视频免费观看| 欧美成人视屏| 国产日韩欧美在线播放| 亚洲福利免费| 国产日韩欧美一区二区三区四区| 欧美h视频在线| 国产精品久久久久久妇女6080 | 欧美日韩成人在线观看| 欧美在线播放高清精品| 欧美黄色一区二区| 久久久久欧美精品| 欧美视频精品在线| 欧美福利网址| 好看的日韩视频| 国产精品99久久久久久久女警| 一区精品久久| 亚洲午夜一级| 在线综合亚洲| 欧美顶级少妇做爰| 老司机aⅴ在线精品导航| 国产精品免费一区二区三区观看| 亚洲国产美女精品久久久久∴| 国内精品伊人久久久久av一坑| 日韩写真在线| 一区电影在线观看| 久久色在线播放| 久久精品视频在线播放| 国产精品狠色婷| 日韩视频免费观看高清在线视频 | 午夜日韩在线| 欧美午夜视频网站| 亚洲美女精品久久| 亚洲理论在线| 欧美大片免费久久精品三p| 美女久久网站| 在线免费精品视频| 久久精品国产精品| 久久视频这里只有精品| 国产专区一区| 久久精品视频免费| 麻豆九一精品爱看视频在线观看免费| 国产精品一区二区久久精品| 亚洲天堂久久| 欧美一乱一性一交一视频| 国产精品露脸自拍| 亚洲在线不卡| 久久国产精品久久久| 国产亚洲精品久久久久久| 亚洲欧美日韩在线不卡| 久久久999| 亚洲福利在线观看| 欧美高清在线一区| 亚洲免费福利视频| 羞羞色国产精品| 国产一区三区三区| 美女主播精品视频一二三四| 亚洲国产成人av好男人在线观看| 日韩视频在线免费| 国产精品久久久久久久久免费樱桃| 在线亚洲精品| 久久精品国产999大香线蕉| 黄色精品一区| 欧美裸体一区二区三区| 一级日韩一区在线观看| 久久精品99无色码中文字幕| 樱花yy私人影院亚洲| 欧美va亚洲va国产综合| 99热在这里有精品免费| 久久激情中文| 99re热这里只有精品免费视频| 国产精品v欧美精品v日韩 | 99视频精品免费观看| 欧美在线3区| 亚洲精品国精品久久99热| 欧美日韩免费高清一区色橹橹| 亚洲免费视频中文字幕| 欧美高清视频一二三区| 午夜精品999| 最新中文字幕亚洲| 国产九区一区在线| 欧美69wwwcom| 欧美一区二区精品在线| 亚洲理伦电影| 猫咪成人在线观看| 亚洲欧美国产视频| 亚洲精品国偷自产在线99热| 国产精品久久久久aaaa樱花| 免费成人高清在线视频| 亚洲综合大片69999| 亚洲欧洲精品成人久久奇米网| 久久福利影视| 国产精品99久久不卡二区 | 欧美精品九九99久久| 久久国产一区| 亚洲免费人成在线视频观看| 亚洲黄色影片| 欧美freesex交免费视频| 欧美一级在线播放| 亚洲天堂成人在线观看| 亚洲日韩第九十九页| 狠狠综合久久| 国产一区二区三区在线观看精品 | 欧美成人日本| 久久亚洲捆绑美女| 欧美在线啊v| 亚洲欧美激情视频| 中文国产亚洲喷潮| 99成人免费视频| 亚洲欧洲在线播放| 亚洲第一级黄色片| 欧美国产日韩亚洲一区| 美女视频黄免费的久久| 欧美一区激情视频在线观看| 亚洲欧美日韩精品综合在线观看| 亚洲欧洲三级| 亚洲精品视频二区| 亚洲精品综合在线| 亚洲免费久久| 亚洲视频在线一区| 亚洲欧美日韩成人| 亚洲女人小视频在线观看| 亚洲视频专区在线| 亚洲欧美激情诱惑| 亚洲欧美变态国产另类| 亚洲欧美在线视频观看| 午夜日韩视频| 久久精彩视频| 美女精品自拍一二三四| 欧美国产第一页| 91久久久国产精品| 99国产精品国产精品久久| 日韩一级视频免费观看在线| 99视频有精品| 亚洲欧美日韩爽爽影院| 欧美在线观看视频一区二区三区 | 欧美一区二区三区免费大片| 欧美一区二区视频97| 久久婷婷国产麻豆91天堂| 欧美不卡在线视频| 亚洲精品你懂的| 亚洲天堂视频在线观看| 性做久久久久久免费观看欧美| 久久精品国产久精国产一老狼| 久久综合中文| 亚洲精品久久久久中文字幕欢迎你| 亚洲精品视频在线观看网站| 亚洲一区激情| 另类综合日韩欧美亚洲| 欧美日韩国产系列| 国产资源精品在线观看| 亚洲免费精彩视频| 久久精品中文字幕一区二区三区 | 午夜在线观看免费一区| 久久久水蜜桃| 99re6这里只有精品| 欧美在线视频免费播放| 欧美精品成人一区二区在线观看 | 国产精品久久久久久久久久久久久久| 国产女主播一区二区| 亚洲国产精品第一区二区| 亚洲天堂网站在线观看视频| 久久视频一区二区| 夜久久久久久| 麻豆精品一区二区综合av | 欧美成人免费在线观看| 国产人妖伪娘一区91| 亚洲免费观看高清在线观看 | 91久久夜色精品国产网站| 亚洲欧美日韩国产综合在线| 欧美96在线丨欧| 国产最新精品精品你懂的| 亚洲婷婷在线| 亚洲国产三级在线| 久久狠狠亚洲综合| 国产精品一区二区你懂的| 亚洲美女在线观看| 欧美成人自拍| 久久久国产成人精品| 国产亚洲视频在线观看|