PAT甲级1131.

目录

A1131

题目

样例

输入:

4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
3
3011 3013
6666 2001
2004 3001

输出:

2
Take Line#3 from 3011 to 3013.
10
Take Line#4 from 6666 to 1306.
Take Line#3 from 1306 to 2302.
Take Line#2 from 2302 to 2001.
6
Take Line#2 from 2004 to 1204.
Take Line#1 from 1204 to 1306.
Take Line#3 from 1306 to 3001.

思路和坑点

　　代码年代久远了，我记得是参考了柳神的代码，这题挺难了，看懂了自己也不一定能独立写得出来。

AC代码

#include<bits/stdc++.h>
using namespace std; 
vector<int> v[10000];
bool vis[10000]={false};                        //占用标记
int mincnt,minTrans,st,ed;                    
unordered_map<int,int> line;
vector<int> path,temppath;
int transfercnt(vector<int> &a){                //换乘统计 
    int cnt=-1,preline=0;                       //cnt计数，preline前一段的路线编号 
    for(int i=1;i<a.size();i++){                //遍历得到的路径 
        if(line[a[i-1]*10000+a[i]]!=preline) cnt++;    //如果当前的线路于上一段不同，说明换乘，计数加一 
        preline= line[a[i-1]*10000+a[i]]; 
    }
    return cnt;
}
void dfs(int node,int cnt){                     //dfs
    if(node==ed){                               //如果到大终点          
        if(cnt<mincnt){                         //如果路径更短。更新 
            mincnt=cnt;
            minTrans=transfercnt(temppath);
            path=temppath;
        }
        else if(cnt==mincnt&&transfercnt(temppath)<minTrans){//如果长度相同，但是换乘更少，也更新 
            mincnt=cnt;
            minTrans=transfercnt(temppath);
            path=temppath;
        }
        return;
    }
    for(int i=0;i<v[node].size();i++){          //递归的dfs搜索node相邻接的顶点 
        int k=v[node][i];
        if(vis[k]==false){
            vis[k]=true;                        //计入路径，并修改标记 
            temppath.push_back(k);        
            dfs(k,cnt+1);        
            vis[k]=false;                       //解除占用 
            temppath.pop_back();                //回上一层 
        }
    }     
}
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n,m,k,pre,temp;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){                    //读入数据 
        scanf("%d%d",&m,&pre);                //第一个结点提前读入 
        for(int j=1;j<m;j++){
            scanf("%d",&temp);
            v[pre].push_back(temp);
            v[temp].push_back(pre);
            line[pre*10000+temp]=line[temp*10000+pre]=i;
            pre=temp;
        }
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++){
        scanf("%d%d",&st,&ed);
        mincnt=99999,minTrans=99999;            //初始化统计变量 
        temppath.clear();                       //其实顶点放入路径 
        vis[st]=true;                           //修改标记 
        temppath.push_back(st);
        dfs(st,0);
        vis[st]=false;                          //解除占用，还原状态 
        printf("%d\n",mincnt);
        int preline=0,pretrans=st;
        for(int j=1;j<path.size();j++){
            if(line[path[j-1]*10000+path[j]]!=preline){
                if(preline!=0) printf("Take Line#%d from %04d to %04d.\n",preline,pretrans,path[j-1]);
                preline=line[path[j-1]*10000+path[j]];
                pretrans=path[j-1];
            }
        }
        printf("Take Line#%d from %04d to %04d.\n",preline,pretrans,ed);
    } 
    return 0;    
}