[最短路]NOI1997：最優乘車 bustravel 解題報告

【描述】
H城是一個旅遊勝地，每年都有成千上萬的人前來觀光。爲方便遊客，巴士公司在各個旅遊景點及賓館，飯店等地都設置了巴士站並開通了一些單程巴上綫路。每條單程巴士綫路從某個巴士站出發，依次途經若干個巴士站，最終到達終點巴士站。

一名旅客最近到H城旅遊，他很想去S公園遊玩，但如果從他所在的飯店沒有一路巴士可以直接到達S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺的另一路巴士, 這樣換乘幾次後到達S公園。

現在用整數1,2,…N 給H城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號爲1,S公園巴士站的編號爲N。

寫一個程序，幫助這名旅客尋找一個最優乘車方案,使他在從飯店乘車到S公園的過程 中換車的次數最少。

輸入輸出

輸入文件的第一行有兩個數字M和N(1<=M<=100 1<N<=500)，表示開通了M條單程巴士綫路，總共有N個車站。從第二行到第M+1行依次給出了第1條到第M條巴士綫路的信息。其中第 i+1行給出的是第i條巴士綫路的信息，從左至右按運行順序依次給出了該綫路上的所有站號相鄰兩個站號之間用一個空格隔開。

輸出文件只有一行。如果無法乘巴士從飯店到達S公園，則輸出"N0"，否則輸出你的程序所找到的最少換車次數，換車次數爲0表示不需換車即可到達

樣例

輸入文件

3 7

6 7

4 7 3 6

2 1 3 5

輸出文件

2

【分析】

最短路徑問題，可以用Floyd算法求解。只是讀入時不太方便，需要先讀一整行。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN=10000000;
int Bus[101][501];
int Map[501][501];
int N,M;

void init()
{
    string line;
    scanf("%d %d\n",&M,&N);
   
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            Map[i][j]=MAXN;
   
    for (int i=1;i<=M;i++)
    {
        Bus[i][0]=0;
        getline(cin,line);
        int tmp=0;
        int len=line.length();
        int top=0;
        while(top<len)
        {
            if(isdigit(line[top]))
            {
                tmp=tmp*10+line[top]-'0';
                top++;
                continue;
            }
            if(line[top]==' ')
            {
                Bus[i][0]++;
                Bus[i][Bus[i][0]]=tmp;
                tmp=0;
                top++;
                continue;
            }
        }
        if(tmp>0)
        {
            Bus[i][0]++;
            Bus[i][Bus[i][0]]=tmp;
        }
    }
   
    int t1,t2;
    for (int i=1;i<=M;i++)
    {
        for (int j=1;j<=Bus[i][0];j++)
        {
            for (int k=j;k<=Bus[i][0];k++)
            {
                t1=Bus[i][j];
                t2=Bus[i][k];
                Map[t1][t2]=0;
            }
        }
    }
}

void Floyd()
{
    int tmp;
    for (int k=1;k<=N;k++)
    {
        for (int i=1;i<=N;i++)
        {
            for (int j=1;j<=N;j++)
            {
                tmp=Map[i][k]+Map[k][j]+1;
                if(tmp<Map[i][j])
                    Map[i][j]=tmp;
            }
        }
    }
    printf("%d\n",Map[1][N]);
}

int main()
{
    freopen("bustravel.in","r",stdin);
    freopen("bustravel.out","w",stdout);
    init();
    Floyd();
    return 0;
}

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	1452 KB	0
2	正确	10	0.000 s	1452 KB	0
3	正确	10	0.001 s	1452 KB	0
4	正确	10	0.000 s	1452 KB	0
5	正确	10	0.003 s	1452 KB	0
6	正确	10	0.003 s	1452 KB	0
7	正确	10	0.001 s	1452 KB	0
8	正确	10	0.003 s	1452 KB	0
9	正确	10	0.003 s	1452 KB	0
10	正确	10	0.308 s	1452 KB	0

运行完成
运行时间 0.325 s
平均内存使用 1452 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
已完成数据库校验。