1131 Subway Map

题意：给出起点和终点，计算求出最短路径（最短路径即所经过的站点最少的），若最短路径不唯一，则选择其中换乘次数最少的一条线路。

思路：本题虽然也是求最短路径，但是此路径是不带权值的，路径长度即所经过的边数，故可以用DFS来求解，而不是用一般的Dijkstra之类的。相信若只是求最短路径，大多数人都会做，就是从起点start开始深度遍历，遍历到终点end时，与全局变量进行比较、更新。本题的关键是，更新最优路径时需要比较“换乘次数”，如何求解它呢？我是这么思考的——首先，考虑用一个二维数组int mp[maxn][maxn]来存储站点与线路的关系，如mp[6666][8432]=4，表示6666->8432是4号线，但考虑到站点编号的范围最大达到9999，也就是数组得开10000*10000，这显然是无法承受的，故选用unordered_map，令unordered_map<int,unordered_map<int,int>> mp，操作和普通的数组一样。（我发现这个unordered_map真的是非常好用，很多题目都可以用，这里不细说，有兴趣的查看文档进行学习）。那么，怎么算是“换乘”呢？假设前一个站是pre，当前站是curr，下一个站是next，若mp[pre][curr]≠mp[curr][next]，说明需要一次换乘，顺序遍历路径path的所有站点，即可求出换乘次数。最后，本题的输出也是比较麻烦，但思路和求换乘次数的方法是一样的。具体请看代码，关键处都有注释。

ps.代码中尽量不要出现中文注释，因为在中文输入法下，若不小心在某一行开头输入了一个空格（难以发现），这会导致编译出错，产生“error: stray '\241' in program”的错误信息。

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <unordered_map>
using namespace std;
;
const int Inf=0x7fffffff;
unordered_map<int,unordered_map<int,int>> mp;//存储两站点间的地铁线，如mp[6666][8432]=4，表示6666->8432是4号线
bool vis[maxn];//在DFS中标记结点是否已经被访问过
vector<int> graph[maxn];//邻接表存储地铁线路图
int k,n,m,s,e,minDistance,minTransfer;//地铁线条数，每条地铁的站点数，查询次数，查询的起点和终点，最短距离，最少换乘数
vector<int> path,tmpPath;//path存放最优路径，tmpPath存放临时路径

int getTransferCnt(vector<int>& path)
{
    ;
    ];
    ;i+<path.size();i++){//注意，这里的判定是i+1<path.size()
        ];
        if(mp[pre][curr]!=mp[curr][next]) changeCnt++;
        pre=curr;//记得更新
    }
    return changeCnt;
}

void dfs(int s)
{
    vis[s]=true;
    tmpPath.push_back(s);
    if(s==e){
        int tmpTransfer=getTransferCnt(tmpPath);
         < minDistance){
            minDistance=tmpPath.size()-;
            minTransfer=tmpTransfer;
            path=tmpPath;
        } == minDistance && tmpTransfer < minTransfer){
            minTransfer=tmpTransfer;
            path=tmpPath;
        }
        return;
    }
    for(auto next:graph[s]){
        if(vis[next] == true) continue;
        dfs(next);
        tmpPath.pop_back();
        vis[next]=false;
    }
}

void printPath(vector<int>& path)
{
    //换乘次数为0时，只需要输出起点和终点，单独输出。这里minTransfer是全局变量，在调用该函数前已经确定
    ){
        ],b=path[path.size()-];//also b=path.back();
        printf(]][path[]],a,b);//注意，这里线路不能是mp[a][b]，因为站点a、b不一定是相邻的！
        return;
    }
    ];//表示当前这条线路的起始站
    ],curr,next;
    ;i+<path.size();i++){
        curr=path[i],next=path[i+];
        if(mp[pre][curr]!=mp[curr][next]) {
            printf("Take Line#%d from %04d to %04d.\n",mp[pre][curr],start,curr);
            start=curr;//出现换乘，记得更新起始站
        }
        pre=curr;
    }
    //输出最后一次换乘至终点的线路
    printf(]][path[path.size()-]],start,path[path.size()-]);
}

int main()
{
    //freopen("pat.txt","r",stdin);
    scanf("%d",&k);
    ;i<=k;i++){
        int pre,curr;
        scanf("%d%d",&n,&pre);
        ;j<n;j++){
            scanf("%d",&curr);
            graph[pre].push_back(curr);
            graph[curr].push_back(pre);
            mp[pre][curr]=mp[curr][pre]=i;
            pre=curr;
        }
    }
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&s,&e);
        //每次查询前千万记得初始化
        memset(vis,false,sizeof(vis));
        path.clear();
        tmpPath.clear();
        minDistance=Inf,minTransfer=Inf;
        dfs(s);
        printf("%d\n",minDistance);
        printPath(path);
    }
    ;
}

巴特西

1131 Subway Map

最新文章

热门文章