ACM 题目：最优乘车

21 July 2014

题目

Problem Description

H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆、饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途径若干个巴士站，最后到达终点巴士站。
一名旅客最近到H城旅游，他很想其S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达S公园。
现在用整数1,2,...N给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。
写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到S公园的过程中换车的次数最少。

Input

有多组输入数据，每组数据的第一行有两个数字M和N(1<=M<=100 1<N<=500)，表示开通了M条单程巴士线路，总共有N个车站。从第2行到第M+1行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。

Output

对于每组数据输出只有一行。如果无法乘巴士从饭店到达S公园，则输出“NO”，否则输出你的程序所找到的最少换车次数，换车次数为0,表示不需换车即可到达。

Sample Input

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

Sample Output

2

解题思路

把巴士路线、站点看成图里面的边和点，因为是不想多换乘，那么可以设定每次换乘的代价是 1，也就是每条边的权值都是 1.
直接套模板，Dijkstra 算法，算出从 1 号站点到 N 号站点的最短路径（因为是换乘次数，所以结果需要减 1）
需要注意的是巴士线路是单程的，所以是有向图，并且同一巴士线路上各站点之间在图的概念上两两连通（假设有一线路 1 → 2 → 3，则认为 1 → 2，2 → 3，1 → 3 都是连通的）；还有就是注意输入数据的效率。

解题代码

//
//  main.cpp
//  最优乘车
//
//  Created by Yeah on 14-7-21.
//  Copyright (c) 2014年 Yeah. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;

#define MAXN 30000
int matrix[501][501];

int Dijkstra(int x, int y, int n) //求有 n 个点的图中，从 x 到 y 的最短路径
{
    int i(0), k(0), path[501], mark[501];
    int min, dist[501];
    for (i = 1; i <= n; i++)
    {
        mark[i] = 0;
        dist[i] = matrix[x][i];
        path[i] = x;
    }
    mark[x] = 1;
    do {
        min = MAXN;
        k = 0;
        for (i = 1; i <= n; i++)
        {
            if (mark[i] == 0 && dist[i] < min)
            {
                min = dist[i];
                k = i;
            }
        }
        if (k)
        {
            mark[k] = 1;
            for (i = 1; i <= n; i++)
            {
                if (matrix[k][i] < MAXN && min + matrix[k][i] < dist[i])
                {
                    dist[i] = min + matrix[k][i];
                    path[i] = k;
                }
            }
        }
    } while (k);
    return dist[y];
}

int main()
{
    int N(0), M(0);
    while (cin >> M >> N)
    {
        getchar();
        
        for (int i(1); i <= N; ++i)
        {
            for (int j(1); j <= N; ++j)
            {
                matrix[i][j] = MAXN;
            }
        }
        
        string line;
        for (int i(0); i != M; ++i)
        {
            vector<int> v;
            char newline('\0');
            int x;
            while (newline != 10)
            {
                scanf("%d", &x);
                v.push_back(x);
                newline = getchar();
            }
            for (vector<int>::iterator it_from(v.begin()); it_from != v.end() - 1; ++it_from)
            {
                for (vector<int>::iterator it_to(it_from + 1); it_to != v.end(); ++it_to)
                {
                    matrix[*it_from][*it_to] = 1;
                }
            }
        }
        
        int dis = Dijkstra(1, N, N);
        if (dis == MAXN)
        {
            cout << "NO" << endl;
        }
        else
        {
            cout << dis - 1 << endl;
        }
    }
    return 0;
}
题目链接：RQNOJ PID263
blog comments powered by Disqus