Subway Map

In the big cities, the subway systems always look so complex to the visitors. To give you some sense, the following figure shows the map of Beijing subway. Now you are supposed to help people with your computer skills! Given the starting position of your user, your task is to find the quickest way to his/her destination.

Input Specification

Each input file contains one test case. For each case, the first line contains a positive integer N(100)N (≤ 100), the number of subway lines. Then N lines follow, with the i-th (i=1,⋯,N) line describes the i-th subway line in the format:

M S[1] S[2] … S[M]

where M(100)M (≤ 100) is the number of stops, and S[i]'s (i=1,⋯,M) are the indices of the stations (the indices are 4-digit numbers from 0000 to 9999) along the line. It is guaranteed that the stations are given in the correct order – that is, the train travels between S[i] and S[i+1] (i=1,⋯,M−1) without any stop. Note: It is possible to have loops, but not self-loop (no train starts from S and stops at S without passing through another station).
Each station interval belongs to a unique subway line. Although the lines may cross each other at some stations (so called “transfer stations”), no station can be the conjunction of more than 5 lines. After the description of the subway, another positive integer K(10)K (≤ 10) is given. Then K lines follow, each gives a query from your user: the two indices as the starting station and the destination, respectively. The following figure shows the sample map. Note: It is guaranteed that all the stations are reachable, and all the queries consist of legal station numbers.

Output Specification

For each query, first print in a line the minimum number of stops. Then you are supposed to show the optimal path in a friendly format as the following:

Take Line#X1 from S1 to S2.
Take Line#X2 from S2 to S3.

where Xi’s are the line numbers and Si’s are the station indices. Note: Besides the starting and ending stations, only the transfer stations shall be printed.
If the quickest path is not unique, output the one with the minimum number of transfers, which is guaranteed to be unique.

Sample Input

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

Sample Output

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<iostream>
#include<unordered_map>
#include<vector>
#define INFINITY 65535
using namespace std;
unordered_map<int,int>lines;           //路线map
bool visited[10100];                   //记录站点是否访问过
vector<int>path,tempath;               //最终路径和每次dfs的备选路径
vector<vector<int>>v(10100);           //图
int mincnt,mintransfer,Start,End,n;    //最少途径站点数、最少换乘次数、起点、终点、路线条数
void buildgraph();
int transfercnt(vector<int>);          //该函数用于求解换乘次数,参数传入的值为备选路径tempath
void SubwayMap();
void dfs(int,int);
// DFS是一个递归函数,考虑递归边界和递归式,
// 递归边界就是到达起点,而递归式更新mincnt和mintransfer以及选择最优路径
// 用tempPath来存放最短的路径,在访问v顶点时就可以把该顶点加入到tempPath中,执行递归式
// 注意之前需要将起点也加入到tempPath中
int main(){
    cin>>n;
    buildgraph();
    SubwayMap();
    return 0;
}
void buildgraph(){
    int m,pre,temp;
    for(int i=0;i<n;i++){              //建图
        cin>>m>>pre;                   //输入每条路线的站点数m和第一个站点pre
        for(int j=1;j<m;j++){          //输入剩下的m-1个站点temp
            cin>>temp;
            v[pre].push_back(temp);    //将pre和temp之间相互增加一条边
            v[temp].push_back(pre);
            lines[pre*10000+temp]=lines[temp*10000+pre]=i+1;
            //记录路线,map第一个关键字前四位为第一个站点,后四位为第二个站点,第二个关键字代表第几条路线
            pre=temp;                  //将temp换为pre,从而将路线上的每两个站点之间增加一条边
        }
    }
}
void SubwayMap(){
    int k;
    cin>>k;                            //输入query个数
    for(int i=0;i<k;i++){
        cin>>Start>>End;               //输入每个query中的起点和终点
        mincnt=mintransfer=INFINITY;   //初始化mincnt和mintransfer
        tempath.clear();               //清空
        tempath.push_back(Start);      //先将起点压入tempath
        visited[Start]=true;           //将起点标记为已访问
        dfs(Start,0);                  //dfs求解最优路径
        visited[Start]=false;          //将起点重新标记为false,准备求解下一个query
        cout<<mincnt<<endl;            //输出最少途经站点
        int preline=0,pretransfer=Start;//定义两个变量用于输出当前路线和站点
        for(int j=1;j<path.size();j++)if(lines[path[j-1]*10000+path[j]]!=preline){
        //如果上一组路线与当前路线不同,按要求的格式输出
                if(preline)printf("Take Line#%d from %04d to %04d.\n",preline,pretransfer,path[j-1]);
                preline=lines[path[j-1]*10000+path[j]],pretransfer=path[j-1];
            }
        printf("Take Line#%d from %04d to %04d.\n",preline,pretransfer,End);//最后输出到终点的那一条边
    }
}
void dfs(int node,int cnt){
    if(node==End){
        if(cnt<mincnt||(cnt==mincnt&&transfercnt(tempath)<mintransfer))
            mincnt=cnt,mintransfer=transfercnt(tempath),path=tempath;
        return;
        //递归出口为node等于终点,同时更新mincnt和mintransfer,选出途径路径和换成次数最少的路径
    }
    for(int i:v[node])if(!visited[i]){//遍历图中未访问站点i,注意这里遍历的是图v的第一个下标
            visited[i]=true;          
            tempath.push_back(i);     //将i压入tempath
            dfs(i,cnt+1);             //递归,途经站点数cnt+1
            visited[i]=false;
            tempath.pop_back();       //递归结束后将站点重新设置为未访问,并弹出tempath,准备求解下一个query
    }
}
int transfercnt(vector<int>a){
//该函数用于求解换乘次数,a传入的值为备选路径tempath
    int cnt=-1,preline=0;             //换乘次数初始化为-1
    for(int i=1;i<a.size();i++){
        if(lines[a[i-1]*10000+a[i]]!=preline)cnt++;//每当tempath中相邻两个站点之间的路线与preline不等时换乘次数+1
        preline=lines[a[i-1]*10000+a[i]];//preline更新为上一组站点的路线
    }
    return cnt;                      //返回换乘次数
} 

Public Bike Management

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city. The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well. When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3, we have 2 different shortest paths:

PBMC -> S1-> S3.

In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1and then take 5 bikes to S3, so that both stations will be in perfect conditions.

PBMC -> S2-> S3.

This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

Input Specification

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax(100)Cmax(≤100), always an even number, is the maximum capacity of each station; N(500)N (≤500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci(i=1,⋯,N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers:

Si, Sj, and Tij

which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space.

Output Specification

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format:

0−>S1−>⋯−>Sp.

Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect. Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge’s data guarantee that such a path is unique.

Sample Input

10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1

Sample Output

3 0->2->3 0

分析

求给定源点和终点之间的最短距离

  • 坑点1:三个标尺,标尺一为dist(源点和终点之间的时间花销最短),标尺二和三分别为从pbmc发出和回收的自行车数量最少
  • 坑点2:发出和回收是按沿途站点依次进行的,因此路径上回收到的自行车只能补充后面的站点,不能补充前面的站点
  • 坑点3:最少发出和回收数量minsend和minback不符合最优子结构,不可以用dijkstra直接求解
    • 即后一个结点的状态不可能由前面的结点推出,不是简单的线性相加关系)
  • 因此本题考虑用dijkstra+dfs的方法求解,djkstra计算dist最短的路径,dfs选择minsend和minback

ac代码

#include<iostream>
#include<stack>
#include<vector>
#include<cmath>
#define MaxVertexNum 550
#define INFINITY 65535
using namespace std;
int capacity,stations,pstation,roads,minsend,minback,
    G[MaxVertexNum][MaxVertexNum],dist[MaxVertexNum];
vector<int>pre[MaxVertexNum],path,tempath;
double station[MaxVertexNum];
bool collected[MaxVertexNum]={false};
void buildgraph();
void pbm();
void dijkstra(int);
void dfs(int);
int findmindist();
int main(int argc,char*argv[]){
    cin>>capacity>>stations>>pstation>>roads;
    buildgraph();
    pbm();
}
void buildgraph(){
    int s,e,t;
    for(int i=0;i<=stations;i++)for(int j=0;j<=stations;j++)if(i!=j)G[i][j]=INFINITY;
    for(int i=1;i<=stations;i++){
        cin>>station[i];
        station[i]-=capacity/2.0;
    }
    for(int i=0;i<roads;i++){
        cin>>s>>e>>t;
        G[s][e]=G[e][s]=t;
    }
}
void pbm(){
    minsend=minback=INFINITY;
    stack<int>stk;
    dijkstra(0);
    dfs(pstation);
    cout<<minsend<<' ';
    for(int i:path)stk.push(i);
    while(stk.size()>1){
        cout<<stk.top()<<"->";
        stk.pop();
    }
    cout<<pstation<<' '<<minback<<endl;
}
void dijkstra(int s){
    for(int i=0;i<=stations;i++){
        dist[i]=G[s][i];
        if((double)G[s][i]<INFINITY)pre[i].push_back(s);
    }
    dist[s]=0,collected[s]=true;
    while(true){
        int v=findmindist();
        if(v<0)break;
        collected[v]=true;
        for(int i=0;i<=stations;i++)if(!collected[i]&&(double)G[v][i]<INFINITY){
            if(dist[i]>dist[v]+G[v][i]){
                dist[i]=dist[v]+G[v][i];
                pre[i].clear(),pre[i].push_back(v);
            }else if(dist[i]==dist[v]+G[v][i])pre[i].push_back(v);
        }
    }
}
int findmindist(){
    int mind=INFINITY,mini=-1;
    for(int i=0;i<=pstation;i++)if(!collected[i]&&mind>dist[i])
        mind=dist[i],mini=i;
    if((double)mind<INFINITY)return mini;
    return -1;
}
void dfs(int node){
    tempath.push_back(node);
    if(node==0){
        int thisend=0,thisback=0;
        for(int i=(int)tempath.size()-1;i>=0;i--){
            int id=tempath[i];
            if(station[id]>0)thisback+=(int)station[id];
            else{
                if(thisback+station[id]>=0)thisback+=(int)station[id];
                else thisend-=(int)(thisback+station[id]),thisback=0;
            }
        }
        if(minsend>thisend||(minsend==thisend&&minback>thisback))
            minsend=thisend,minback=thisback,path=tempath;
        tempath.pop_back();
        return;
    }
    for(int i:pre[node])dfs(i);
    tempath.pop_back();
}