[34]公交车-美团点评2018秋

1.题目描述

一座城市有n个公交站点，站点从1到n编号，和m班公交车，公交车从1到m编号，乘坐每班公交车只需花费1元钱。第i班公交车一共经过t_i个站点，分别为站点a_(i,1),a_(i,2),…,a_(i,t_i)，小明可以乘坐第i班公交车从这t_i个站点中的任意一个到达任意另一个站点。如一班公交车经过站点1,2,3，那么小明花费1元钱就可以从1到2，从1到3，从2到1，从2到3，从3到1，从3到2。小明想从1号站点到n号站点，问他最少花费多少钱。
*输入描述:
第一行两个数n,m。(2≤n≤100000,1≤m≤100000)
接下来m行，依次描述每班公交车经过的站点，第i行开头一个数t_i，表示第i班公交经过的站点数，
接下来t_i个数，依次表示这t_i个站点。(2≤t_i≤n,∑(i=1)^m，t_i≤100000)
*输出描述:
输出一个数，从1号站点到n号站点的最小代价，如果不能达到，输出-1。

• 输入示例：

  5 3
  3 1 2 3
  3 3 4 2
  3 3 5 4
  

• 输出示例:

  2
  

• 样例解释：
  先坐第1班公交从1号站点到3号站点，再做第3班公交从3号站点到5号站点，一共花费2元。

2.题目解析

站点与公交车之间的关系。

把公交车看成一个图上的节点

因为站点的编号从1到n，公交车的编号从1到m，存在重复。所以，把公交车的编号改为从n+1到n+m。

问题变成从站点1到n最短距离。

注意每个站点中间增加了公交车节点，最后求解的距离要除以2。

• 同一站点经过的公交车

  
  

• 同一辆公交车通过的站点

  
  

图的最短距离，求出从起点到所有点的最短距离。

3.参考答案

#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);
}

牛客题目