Write in front

• Thought analysis
  • Find a lane so that for any given starting point and end point, the lane with the least stops can be found.
    • If there are more than one stops, take the least number of transfer routes.
  • Once DFS
    • Maintaining two variables in DFS process
      • minCnt - Minimum stopping station
      • minTransfer - Minimum number of transfers required
    • 0. Calculate the transfer times of one line:
      • In the line[10000][10000] array, which number of lines are stored in the middle of each two adjacent stations?
      • Traversing the final saved path from beginning to end, preLine is the line number of the first segment. If the line number of the current node and the first node is different from that of the preLine, it means that there is a transfer, cnt+1 will be used, and the number of transfers will be the number of times after traversing the accumulated cnt.
      • Unordered_map < int, int > line storage mode is selected. The first int storage line stores the first four bits of line at a time, and the second four bits of line at a time. The second int stores the two adjacent middle lines in a[i-1]*10000+a[i]. The second int stores the number of lines.
    • 1. Calculate the number of stops in the middle of a line:
      • In dfs, there is a variable cnt, which indicates that the current route is the number of stations to multiply. Each dfs, cnt+1 is represented as traversing down one layer.
        • cnt is the current number of stops
    • 2. Output results:
      • The same idea as the number of line transfers is used to output a dialog whenever the preLine and the current Line values are not the same.
      • Save preTransfer to represent the last transfer station
      • The final output is between the preTransfer and the last station, even if the last station is not a transfer station.
• Long and difficult topics, learning ing

test case

• 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
  
  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 code

• #include <iostream>
  #include <vector>
  #include <unordered_map>
  using namespace std;
  
  vector<vector<int>> v(10000);
  int visit[10000], minCnt, minTransfer, start, end1;
  unordered_map<int, int> line;
  vector<int> path, tmpPath;
  
  // Statistical number of transfer routes
  int transferCnt(vector<int> a)
  {
      int cnt = -1, preLine = 0;
      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)
  {
      // Terminal/transfer times are less than minimum/transfer times are equal to minimum and transfer routes are less than minimum transfer routes
      if(node == end1 && (cnt < minCnt || (cnt == minCnt && transferCnt(tmpPath)<minTransfer)))
      {
          minCnt = cnt;
          minTransfer = transferCnt(tmpPath);
          path = tmpPath;
      }
      if(node == end1) return;
      for(int i=0; i<v[node].size(); i++)
      {
          if(visit[v[node][i]] == 0)
          {
              visit[v[node][i]] = 1;
              tmpPath.push_back(v[node][i]);
  
              // Don't quite understand
              dfs(v[node][i], cnt+1);
              visit[v[node][i]] = 0;
              tmpPath.pop_back();
          }
      }
  }
  
  int main()
  {
      int n, m, k, pre, tmp;
      scanf("%d", &n);
  
      // Batch Read-in Circuit
      for(int i=0; i<n; i++)
      {
          scanf("%d%d", &m, &pre);
          for(int j=1; j<m; j++)
          {
              scanf("%d", &tmp);
              v[pre].push_back(tmp);
              v[tmp].push_back(pre);
              // Labeled Circuit
              line[pre*10000+tmp] = line[tmp*10000+pre] = i+1;
              // Update successor nodes
              pre = tmp;
          }
      }
  
      scanf("%d", &k);
      for(int i=0; i<k; i++)
      {
          scanf("%d%d", &start, &end1);
          minCnt = 9999, minTransfer = 9999;
          tmpPath.clear();
          tmpPath.push_back(start);
  
          visit[start] = 1;
          dfs(start, 0);
  
          visit[start] = 0;
          printf("%d\n", minCnt);
  
          int preLine = 0, preTransfer = start;
          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, preTransfer, path[j-1]);
                  preLine = line[path[j-1]*10000+path[j]];
                  preTransfer = path[j-1];
              }
          }
          printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, end1);
      }
  
      return 0;
  }
  	```
  

• Learning code
  • I don't understand it very well. Follow-up study

  #include <stdio.h>
  #include <stdlib.h>
  #define inf 0x3f3f3f3f
  #define MAX 10002
  int n,m,k;
  int link[MAX][11],linknum[MAX];//Number of adjacent elements
  int vis[MAX],path[MAX],num,ans[MAX],ant;
  int line[MAX][11];//Lines to which adjacent elements belong
  int getline(int a,int b)  //Get the line number
  {
      for(int i = 0; i < linknum[a]; i ++)
          if(link[a][i] == b)return line[a][i];
  }
  void dfs(int stop,int lastline,int lnum,int snum,int des)  //stop is the current station lastline is the last line of the last line, lnum is the current number of transfer stations snum is the number of stations des is the destination
  {
      path[snum] = stop;
      if(snum > ant || snum == ant && lnum > num)return;
      if(stop == des)
      {
          ant = snum;
          num = lnum;
          for(int i = 0; i <= snum; i ++)
          {
              ans[i] = path[i];
          }
          return;
      }
      for(int i = 0; i < linknum[stop]; i ++)
      {
          if(!vis[link[stop][i]])
          {
              vis[link[stop][i]] = 1;
              int d = getline(stop,link[stop][i]);
              if(lastline != d)dfs(link[stop][i],d,lnum + 1,snum + 1,des);
              else dfs(link[stop][i],d,lnum,snum + 1,des);
              vis[link[stop][i]] = 0;
          }
      }
  }
  int main()
  {
      int a,b;
      scanf("%d",&n);
      for(int i = 1; i <= n; i ++)
      {
          scanf("%d",&m);
          scanf("%d",&a);
          for(int j = 1; j < m; j ++)
          {
              scanf("%d",&b);
              link[a][linknum[a] ++] = b;
              line[a][linknum[a] - 1] = i;
              link[b][linknum[b] ++] = a;
              line[b][linknum[b] - 1] = i;
              a = b;
          }
      }
      scanf("%d",&k);
      while(k--)
      {
          scanf("%d%d",&a,&b);
          ant = num = MAX;
          dfs(a,-1,-1,0,b);
          printf("%d\n",ant);
          int line1 = getline(ans[0],ans[1]);
          for(int i = 2; i <= ant; i ++)
          {
              int line2 = getline(ans[i - 1],ans[i]);
              if(line1 != line2)
              {
                  printf("Take Line#%d from %04d to %04d.\n",line1,a,ans[i - 1]);
                  a = ans[i - 1];
                  line1 = line2;
              }
          }
          printf("Take Line#%d from %04d to %04d.\n",line1,a,ans[ant]);
      }
      return 0;
  }