267. [NOI1999] 最优乘车

澳门行·摄

文|秋锐

罗萨里奥,最初的记念莫过于大三巴和娱乐城了。第贰次去火奴鲁鲁早就是不少年前了,当年跟团旅行,赶鸭子似的赶行程,对金沙萨的影像也只就只是留在所谓的大三巴妈祖阁和威郑州人。

那1次游玩,时间说不上丰富,但也算知足了。从老城到新城,再回来也门萨那本来的渔村,丰富感受到了那座东西组成的小城风情。

万事行程虽说有一天半,但确确实实的都汇聚在了第三天,第叁天纯粹是睡觉睡到自然醒。

John四世马来西亚路

民政总署

议事厅前地

仁慈堂大楼

仁慈堂旁的小街(是还是不是很有FELL)

玫瑰堂与提示牌

正午逛完了大三巴,品尝了猪扒包。本来打算先回酒店放东西,无奈酒馆索要三点后才能拿房,于是遍继续接着布署的路程走,到路环吃蛋挞。在亚马喇前地站,经过嘉乐庇总督大桥,从老的华雷斯半岛,经过金壁辉煌的娱乐城,坐着公共交通车驶来了路环,随着填海造地,凼仔和路环早已亲密无间的持续。和红火的凼仔截然分裂,那里远离吕梁市核心的沸沸扬扬,越发平静。

路环市区·恩哈利法克斯总理前地

选取到路环,也实在要到此品尝一下Andrew蛋挞,安德鲁是汉森尔顿葡挞的开山,那年开店也选择在了最具有乡野气息的离岛路环。大概挺几个人来火奴鲁鲁都会去白云区里玛嘉烈,终究波尔多最有名的蛋挞正是Andrew和玛嘉烈了吗。其实她们是夫妻关系,离婚后,拥有了Andrew蛋挞配方的玛嘉烈另起炉灶跟Andrew唱起了对台戏。更决心的是,还把配方传给了肯德基,所以未来国内肯德基的蛋挞也得以算是Andrew的配方吧。

安德鲁咖啡

感受一下小资小调的生存

此处还会提到,在安德鲁有三个分店,3个咖啡为主,三个便是蛋挞作坊,而作者先选取在角落可吃正餐,也正是那所金黄的欧式小楼。点餐的时候,小编才意识此处的职工都以法国人,东南亚为主吧,他们听不懂普通话呢,必要用立陶宛(Lithuania)语沟通的,价格不贵,蛋挞酥脆,焦糖味香。

船人街

码头拥有金沙萨仅存的棚屋

海鲜干货店

路牌

路环码头

路环码头曾于1873年修建,在路凼连贯公路及嘉乐庇桥梁没有形成的年份,路环码头是温尼伯的公交码头,作为小轮由路环往返澳凼的停泊处。路环码头昔日曾是昆明重点的码头之一,随着大桥及道路兴建,其职能已不复再,令人怀缅。

码头岸边的横琴

圣方济各教堂

基于教堂建于1926年,后边的回想碑是怀念1907年克服海盗。

是因为赶行程,所以路环的小街小巷和黑沙沙滩就不曾去一探毕竟了,但初略的漫游了路环的表明景点,这里不光充满浓郁澳国风情的异邦小城,更有实在的Cordova的渔村,别样风情让人备感舒畅女士惬意。从渔村到赌城,阿瓜斯卡连特斯过去的相貌曾经模糊不清不可辨,也只还好离家市区的路环才能体会到过去的渔村滋味。一点也不慢的坐车回去了凼仔,同样也有多个醒指标痛感。今昔非彼,和本人刻钟候来新奥尔良巡游,那里早已是刚刚开发的填海区,今后已是各大娱乐城的聚集地。逛完了新濠影汇,香水之都人和威罗萨利奥人,走出酒馆天色已黑。

金沙城与喜来登

新濠天地

出于夜间意想不到的灰霾,也就在自家拍完埃菲尔石塔后,阴霾笼罩了方方面面路凼。就快速坐车会阿瓜斯卡连特斯半岛了。回到卡托维兹半岛也已经快早晨了,好多合营社都关门了,一切都来得极冷静,而此刻的玩耍场内又是另一番世界了。

老葡京娱乐场

享受一张老葡京饭馆西座大堂,就如回到了上世纪90年份的时节。究竟老葡京建于上世纪70时代了,从外观到里面,都是三个一时的布置性风格的知情人。

西座大会堂

晚上太困,睡到自然醒,外出吃早餐时增选了周边的弄堂,周末的弄堂也显得的安静。

5588葡京线路,波德戈里察虽小,用一两日的岁月感受当地的人情世故风味却如故不够。

本次旅行告一段落,未来有时光有机会,恐怕还会再来一趟,越发深远的攒走小街小巷,融进阿拉木图本地的生活方法去感受。

当然还想再多上传一些照片,但本身文章首发于公号“传说比跳蚤还多”。发文时自个儿也控制了图片数量,所以这边宣布也不再上传了,也还迎我们多多关心帮衬微信公众号:典故比跳蚤还多。

★★   输入文件:bustravel.in   输出文件:bustravel.out   不难比较

岁月范围:1 s   内部存款和储蓄器限制:128
MB

H城是3个旅游胜地,每年都有广大的人前来旅游。为方便旅客,巴士公司在依次旅游景点及旅馆,酒馆等地都安装了巴士站并开通了一部分单程巴上线路。每条单程巴士线路从某些巴士站出发,依次途经若干个巴士站,最后抵达顶峰巴士站。

一名游客近年来到H城环游,他很想去S公园游玩,但一旦从她四处的饮食店没有联手巴士能够一贯抵达S公园,则他恐怕要先乘某伙同巴士坐几站,再下来换乘同一站台的另一只巴士,
那样换乘三次后到达S公园。

现行反革命用整数1,2,…N
给H城的全部的巴士站编号,约定这名游客所在茶馆的巴士站编号为1,S公园巴士站的号码为N。

写一个程序,扶助那名游客寻找八个最优乘车方案,使她在从客栈乘车到S公园的进程中换车的次数最少。

输入输出

输入文件的率先行有五个数字M和N(1<=M<=100
1<N<=500),表示开通了M条单程巴士线路,总共有N个车站。从第1行到第M+1行各类给出了第③条到第M条巴士路线的消息。个中第
i+1行提交的是第i条巴士路线的音讯,从左至右按运营顺序依次给出了该线路上的具备站号相邻多少个站号之间用1个空格隔绝。<n<=500),表示开通了m条单程巴士路线,总共有n个车站。从第1行到第m+1行一一给出了第壹条到第m条巴士路线的新闻。在那之中第
p=””
i+1行给出的是第i条巴士路线的新闻,从左至右按运维顺序依次给出了该线路上的保有站号相邻多个站号之间用三个空格隔离。<=””>

出口文件唯有一行。要是不可能乘巴士从旅社到达S公园,则输出”N0″,不然输出你的主次所找到的至少换车的车的班次数,换车的车的班次数为0代表不需换车即可抵达

样例

输入文件

3 7
6 7
4 7 3 6
2 1 3 5

输出文件

2

#include<iostream> 
#include<vector>
#include<cstdio>
#include<cstring>

using namespace std;
const int INF=9999999;

int n,m,c,x,a[101][501],f[501][501];

void read()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)    
        for(int j=1;j<=n;j++)
            f[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
        c=0;char b=' ';
        while(b!='\n'/*&&b!='/r'*/)
        {
            scanf("%d",&x);b=getchar(); 
            a[i][++c]=x;
            for(int j=1;j<c;j++)
                f[a[i][j]][x]=1;
        }
    }
    for(int i=1;i<=n;i++)f[i][i]=0;
}

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
}

int main()
{
    freopen("bustravel.in","r",stdin);
    freopen("bustravel.out","w",stdout);
    read();
    floyd();
    if(f[1][n]>=INF)printf("NO\n");
    else printf("%d\n",f[1][n]-1);
    return 0;
}