算法提高之最优乘车

算法提高之最优乘车

• 核心思想：最短路

  • 

  • 将一条路上所有点依次连边: 1->2->3 就将g[1][3] = g[1][2] = g[2][3] = true 边权默认为1

  • 因为边权为1 所以bfs求最短路即可

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    const int N = 510;
    int n,m;
    int dist[N];
    int stop[N];
    int q[N];
    bool g[N][N];
    
    void bfs()
    {
        memset(dist,0x3f,sizeof dist);
        dist[1] = 0;
        q[0] = 1;
        int hh = 0, tt = 0;
        
        while(hh<=tt)
        {
            int t = q[hh++];
            for(int i=1;i<=m;i++)
            {
                if(g[t][i] && dist[i] > dist[t] + 1)
                {
                    dist[i] = dist[t] + 1;
                    q[++tt] = i;
                }
            }
        }
    }
    int main()
    {
        cin>>n>>m;
        string line;
        getline(cin,line);
        while (n -- )
        {
            getline(cin,line);
            stringstream ssin(line);  //输入
            int cnt=0,p;
            while(ssin >> p) stop[cnt++] = p;  //取出每一个数
            for(int j=0;j<cnt;j++)
                for(int k=j+1;k<cnt;k++)
                    g[stop[j]][stop[k]] = true;
        }
        
        bfs();
        
        if(dist[m] == 0x3f3f3f3f) puts("NO");
        else cout<<max(dist[m] - 1,0)<<endl;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54