• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 218039
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜


            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 閱讀(571) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            久久综合久久综合亚洲| 人妻丰满?V无码久久不卡| 久久久久久久久波多野高潮| 国产精品成人久久久| 国产一级持黄大片99久久| 久久精品视屏| 久久精品国产精品亚洲毛片| 一个色综合久久| 久久久久免费看成人影片| 精品99久久aaa一级毛片| 女人香蕉久久**毛片精品| 亚洲级αV无码毛片久久精品| 久久乐国产精品亚洲综合| 99久久精品费精品国产| 久久久久久久综合日本亚洲| 久久伊人色| 久久亚洲国产精品一区二区| 亚洲午夜精品久久久久久app| 久久久久久国产a免费观看不卡| 性欧美丰满熟妇XXXX性久久久| 久久人人爽人人爽人人片AV麻豆| 97精品久久天干天天天按摩 | 久久99精品久久久久久hb无码| 久久亚洲精品无码aⅴ大香| 久久精品国产99国产精品澳门| 久久精品卫校国产小美女| 久久综合狠狠综合久久激情 | 日韩人妻无码一区二区三区久久| 亚洲精品国产第一综合99久久| 久久久国产精品福利免费| 亚洲AV无码久久精品色欲| 欧洲性大片xxxxx久久久| 88久久精品无码一区二区毛片| 国产国产成人精品久久| 亚洲国产欧洲综合997久久| 伊人热热久久原色播放www| 亚洲国产日韩欧美综合久久| 人人狠狠综合久久亚洲| 久久久中文字幕日本| 尹人香蕉久久99天天拍| 久久久久亚洲av综合波多野结衣 |