公交车

原来有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);
    }
}

动态规划
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);
        }
    }
}