公交车

C++ 解法, 执行用时: 29ms, 内存消耗: 7084KB, 提交时间: 2021-07-07

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 0;// 站点数
  int m = 0;// 公交车数
  scanf("%d%d", &n, &m);
  int nums = n+m+2; // 图的节点数
  vector<int> vec[nums]; // 从1开始
  // 建图同一辆公交车通过的点建一条边到这辆公交车的抽象点，再从抽象点建一条边到这些点
  for (int i = 1; i <= m; i++) {
    int t = 0;
    scanf("%d", &t); // 公交车数经过站点数
    for (int j = 1; j <= t; j++) {
      int a = 0;
      scanf("%d", &a); // 公交车数经过站点
      vec[a].push_back(i+n); // 同一站点经过的公交车
      vec[i+n].push_back(a); // 同一辆公交车通过的站点
    }
  }
  queue<int> q;              // 定义队列
  int visited[nums];           // 定义标记顶点是否已访问
  fill_n(visited,nums,-1);   // 初始化为未访问
  visited[1] = 0;            // 标记v已经访问
  q.push(1);                 // 入队v
  while (!q.empty()) {       // 队列非空
    int now = q.front();     // 取出队首元素
    q.pop();                 // 队首元素出队
    for (int i = 0; i < vec[now].size(); i++) { // 遍历v的邻接点
      int post = vec[now][i];// 取出邻接点
      if (-1 == visited[post]) {  // 判断邻接点是否访问
        visited[post] = visited[now]+1;// 标记邻接点已访问
        q.push(post);        // 邻接点入队
      }
    }
  } 
  if(-1 == visited[n]) printf("-1\n");
  else printf("%d\n",visited[n]/2);
  return 0;
}

C++14 解法, 执行用时: 30ms, 内存消耗: 7036KB, 提交时间: 2019-04-27

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 0;// 站点数
  int m = 0;// 公交车数
  scanf("%d%d", &n, &m);
  int nums = n+m+2; // 图的节点数
  vector<int> vec[nums]; // 从1开始
  // 建图同一辆公交车通过的点建一条边到这辆公交车的抽象点，再从抽象点建一条边到这些点
  for (int i = 1; i <= m; i++) {
    int t = 0;
    scanf("%d", &t); // 公交车数经过站点数
    for (int j = 1; j <= t; j++) {
      int a = 0;
      scanf("%d", &a); // 公交车数经过站点
      vec[a].push_back(i+n); // 同一站点经过的公交车
      vec[i+n].push_back(a); // 同一辆公交车通过的站点
    }
  }
  queue<int> q;              // 定义队列
  int visited[nums];           // 定义标记顶点是否已访问
  fill_n(visited,nums,-1);   // 初始化为未访问
  visited[1] = 0;            // 标记v已经访问
  q.push(1);                 // 入队v
  while (!q.empty()) {       // 队列非空
    int now = q.front();     // 取出队首元素
    q.pop();                 // 队首元素出队
    for (int i = 0; i < vec[now].size(); i++) { // 遍历v的邻接点
      int post = vec[now][i];// 取出邻接点
      if (-1 == visited[post]) {  // 判断邻接点是否访问
        visited[post] = visited[now]+1;// 标记邻接点已访问
        q.push(post);        // 邻接点入队
      }
    }
  } 
  if(-1 == visited[n]) printf("-1\n");
  else printf("%d\n",visited[n]/2);
}

详情