Minimum transfer times

Minimum transfer times

Problem description :

Let a city have n A station , And there are m A bus line connects these stations . All these buses are one-way , this n Stations are numbered sequentially as 0~n-1. Numbering procedure , Enter the number of bus lines in the city , Number of stations , And the number of each station on each bus line .

Fulfill the requirements ：

Get slave station 0 Start by bus to the station n One 1 The minimum number of changes .

Ideas ：

BFS: We connect all the stations on the same line to one side , So you can use it directly bfs Find the shortest distance , because bfs It must be the shortest as long as we reach the end .

Single source shortest path algorithm ： classical Dijstra Algorithm to find the shortest path

#include<iostream>
#include<sstream>
#include<cstring>
#include<algorithm>
#include<queue>
// The first line has two numbers M and N, It means it's open M A one-way bus route , All in all N A station .
// From the second line to M+1 The row in turn gives the number 1 To the first article M Information about this bus route , Among them the first i+1 Line gives the number i Information about this bus route ,
//  All station numbers on the line are given in sequence from left to right , Two adjacent station numbers are separated by a space .
using namespace std;
const int N=510,inf=0x3f3f3f3f;

int n,m;  //n A station 
bool g[N][N];
int dis[N];   // Used to store the shortest path 

void bfs()
{
    
    memset(dis,0x3f,sizeof dis);

    queue<int> Q;
    Q.push(1);
    dis[1]=0;

    while(Q.size())
    {
    
        int u=Q.front();
        Q.pop();

        for(int i=1;i<=n;i++)
            if(g[u][i] && dis[i]>dis[u]+1)
            {
    
                dis[i]=dis[u]+1;
                Q.push(i);
            }
    }
}

void dijstra(int start)
{
    
    //dijstra Algorithm start 
    //visited Array initialization 
    int visited[n+1];
    memset(visited,0,sizeof(visited));
    visited[start]=1;

    //dist Array initialization 
// int dist[n+1];
    for(int i=1;i<=n;i++){
    
        if(g[start][i]) dis[i] = 1;
        else dis[i] = inf;
    }

    for(int i=2;i<=n;i++){
    
        int min = 99999, u;
        // Find the edge with the smallest path in the current state 
        for(int i=1;i<=n;i++){
    
            if(!visited[i] && dis[i]<min){
    
                min = dis[i];
                u = i;
            }
        }
        // take u Add to s aggregate ,visited[u]=1;
        visited[u]=1;
        // Update shortest path 
        for(int i=1;i<=n;i++){
    
            if(!visited[i] && g[u][i] && dis[u]+1<dis[i]){
    
                dis[i] = dis[u]+1;
            }
        }
    }

}

int main()
{
    
    printf("===================== Start mapping ====================\n");
    printf(" Please enter the number of bus lines  and  Number of bus stops :\n");
    cin>>m>>n;
    int to = m;

    string line;
    getline(cin,line);
    while(m--)
    {
    
        printf(" Please enter the first %d The station that this line passes through , Space off ：\n",to-m);
        getline(cin,line);
        stringstream ssin(line);
        int p[N],cnt=0;

        while(ssin>>p[cnt]) cnt++;
        for(int i=0;i<cnt;i++)
            for(int j=i+1;j<cnt;j++)
                g[p[i]][p[j]]=true;
    }

// bfs();
    dijstra(1);

//  Because the edge weights between platforms in the same line are 1, So when running the shortest way , At most two stations pass through the same line .
//  And because the boundary rights are 1, Therefore, the shortest circuit can be bfs To run .
//  The result we get is the minimum number of buses we have taken , And the number of transfers has to be reduced 1.
    printf("===================== Query start ====================\n");
    while(true){
    
        printf(" Please enter the destination you want to reach ,-1 Exit ：\n");
        int tar; cin>>tar;
        if(tar==-1) break;
        if(tar>n){
    
            printf(" Illegal input , Please re-enter \n");
            continue;
        }

        if(dis[tar]==inf) puts("NO");
        else cout<<" Congratulations ! The destination can be reached by car , The minimum number of transfers is ："<<max(dis[tar]-1,0)<<endl;
    }

    printf("===================== Welcome to the system ====================\n");
    return 0;
}

// The test sample 
//3 7
//6 7
//4 7 3 6
//2 1 3 5
//2