公交车

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author wylu
 */
public class Main {
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]);
        graph = new ArrayList[n + m + 1];

        //建图, 将公交车抽象成一个站点, 只记录公交车到相应站点的边
        for (int i = 1; i <= m; i++) {
            strs = br.readLine().split(" ");
            graph[i + n] = new ArrayList<>();
            for (int j = 1; j < strs.length; j++) {
                int station = Integer.parseInt(strs[j]);
                if (graph[station] == null) graph[station] = new ArrayList<>();
                graph[station].add(i + n);
                graph[i + n].add(station);
            }
        }

        //bfs求最短路, 
        int res = bfs(1, n, m);
        //因为设立了抽象点,起点距离又设为1,所以每个点的距离是实际距离的两倍加一
        System.out.println(res == 0 ? "-1" : res / 2);
    }

    private static int bfs(int x, int n, int m) {
        int[] dist = new int[n + m + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        dist[x] = 1;
        queue.offer(x);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (Integer e : graph[cur]) {
                if (dist[e] == 0) {
                    dist[e] = dist[cur] + 1;
                    queue.offer(e);
                }
            }
        }
        return dist[n];
    }
}

#include <bits/stdc++.h>

using namespace std;

vector<int> Adj[200003];
int d[200003];

int BFS(int s, int e)
{     queue<int> q;     q.push(s);     d[1] = 1;     while(!q.empty())     {         int p = q.front();         q.pop();         for(int i=0;i<Adj[p].size();i++)         {             if(d[Adj[p][i]]==0)             {                 d[Adj[p][i]] = d[p] + 1;                 q.push(Adj[p][i]);             }         }     }     if(d[e]==0)         return -1;     else         return d[e]/2;     }

int main()
{     int n,m;     while(cin>>n>>m)     {         int t,u,v;         for(int i=1;i<=m;i++)         {             cin>>t;             for(int j=1;j<=t;j++)             {                 cin>>u;                 Adj[u].push_back(i+100000);                 Adj[i+100000].push_back(u);             }         }         cout<<BFS(1,n)<<endl;     }     return 0;
}

	

原来有n个公交车站，有m条公交线路。对于其中一条线路a->b->c,使得a,b,c三个公交车站距离变成了1（1块钱可以到达）。因此，我们建立无向图（边全值为1）。但是公交线路长度很长（2<=t <=100000），这样对一个公交线路来说，建边复杂度为。为了降低复杂度，每个线路都建立一个虚拟节点，使得公交车站通过虚拟节点相连接，这样就减少了边的数量,这样对一个公交线路来说，建边复杂度为。对于对于其中一条线路a->b->c， 建立一个节点x，如果要求a到b的距离，a,b之间并没有直接边相连，而是通过x节点，间接相连（a->x->b)。因此，我们将边的权值设为0.5，a到b的权值就仍然为1。问题还是求1-n的距离。

import java.util.*;
public class Main {
    static int bfs(List<Integer>[] g, int n){
        boolean[] used = new boolean[g.length];
        LinkedList<Integer> q = new LinkedList<>();
        q.offer(1); used[1] = true;
        int distance = 0;
        while(!q.isEmpty()){
            int size = q.size();
            distance ++;
            for(int i=0; i < size; i++) {
                int cur = q.poll();
                for(int j=0; j <g[cur].size(); j++) {
                    int v = g[cur].get(j);
                    if(v == n) return distance/2;
                    if(used[v] == false) {
                        used[v] = true;
                        q.offer(v);
                    }
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        List[] g = new ArrayList[n+m+1];
        for(int i=1; i < g.length; i++) g[i] = new ArrayList<Integer>();
        for(int i=1; i <= m; i++) {
            int t = sc.nextInt();
            for(int j=1; j <= t; j++) {
                int v = sc.nextInt();
                g[n+i].add(v);
                g[v].add(n+i);
            }
        }
        int res = bfs(g, n);
        System.out.println(res);
    }
}

n,m = list(map(int,input().split()))
edges = []
for _ in range(m):
    t = list(map(int,input().split()))
    for i in range(1,t[0]):
        for j in range(i+1,t[0]+1):
            edges.append([t[i],t[j]])
adjacent = {}
for index in range(1,n+1):
    adjacent[index] = []
for i in range(len(edges)):
    if edges[i][1] not in adjacent[edges[i][0]]:
        adjacent[edges[i][0]].append(edges[i][1])
    if edges[i][0] not in adjacent[edges[i][1]]:
        adjacent[edges[i][1]].append(edges[i][0])

def bfs(route,cost):
    flag = True
    if route[-1] == 5:
        project.append(cost)
        flag = False
    if flag:
        for next_station in adjacent[route[-1]]:
            if next_station not in route:
                bfs(route+[next_station],cost+1)

project = []
route = [1]
cost = 0
bfs(route,cost)
print(min(project))

动态规划
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s=new Scanner(System.in);
        int z=s.nextInt();
        int bn=s.nextInt();
        int[] an=new int[z];
        List<Set<Integer>> cunList=new ArrayList<Set<Integer>>();
        for (int i = 0; i < z; i++) {
            an[i]=200000;
        }
        for (int i = 0; i < bn; i++) {
            int flag=0;
            Set<Integer> temp=new TreeSet<Integer>();
            int m1=s.nextInt();
            for (int j = 0; j < m1; j++) {
                int t1=s.nextInt();
                temp.add(t1);
                if (t1==1) {
                    flag=1;
                }
            }
            if (flag==1) {
                for (Integer integer : temp) {
                    an[integer-1]=1;
                }
            }else {
                cunList.add(temp);
            }
        }
        int min=200000;
        for (Set<Integer> set : cunList) {
            min=200000;
            for (Integer zz : set) {   //遍历对比该车每一站                          
            if (an[zz-1]!=200000&&an[zz-1]<min) {
                min=an[zz-1];
            }    
            }
            for (Integer zz : set) {
                if ((min+1)<an[zz-1]) {
                    an[zz-1]=min+1;
                }
            }
        }
        if (an[z-1]<200000) {
            System.out.println(an[z-1]);
        }else {
            System.out.println(-1);
        }
    }
}