算法1 dijkstra算法

// dijkstra算法
import java.util.*;
public class Main {
    static int N = 410;
    static int INF = 0x3f3f;
    static int n,m;
    static int[][] g0 = new int[N][N];//铁路
    static int[][] g1 = new int[N][N];//公路
    static int [] d = new int [N];
    static boolean [] use;

    static int dijkstra(int [][] g){
        if(g[1][n]==1) return 1;

        use = new boolean [N];
        Arrays.fill(d, INF);
        d[1] = 0;
        for(int i = 1;i <= n;i++){
            int t = -1;
            for(int j = 1;j <= n;j++){
                if(!use[j]&&(t==-1 || d[t]>d[j])){
                    t = j;
                }
            }
            use[t] = true;//该点已经使用过
            // 更新d[]
            for(int j = 1;j <= n;j++){
                d[j] = Math.min(d[j],d[t]+g[t][j]);
            }
        }
        return d[n];
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();m = sc.nextInt();

        for(int i = 1;i <= n;i++){
            Arrays.fill(g0[i], INF);
            Arrays.fill(g1[i], INF);
        }

        for(int i = 1;i <= m;i++){
            int a = sc.nextInt();int b = sc.nextInt();
            g0[a][b]=g0[b][a] = 1;
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j < i;j++){
                if(g0[i][j]!=1){
                    g1[i][j] = g1[j][i] = 1;
                }
            }
        }

        // 0表示铁路，1表示公路
        int result = Math.max(dijkstra(g0), dijkstra(g1));
        if(result>=INF) result = -1;
        System.out.println(result);
    }
}

算法2 spfa算法

// spfa算法
import java.util.*;
public class Main {
    static int N = 410,M = 160010;
    static int INF = 0x3f3f;
    static int n,m;
    static int[] d = new int[N];// 点到起始点的距离
    static boolean [] use ;//点是否在队列中
    static int [][] g = new int [N][N];//记录铁路邻接矩阵
    static int [] h0 = new int [N];//铁路的邻接表
    static int [] h1 = new int [N];//公路的邻接表
    static int [] e = new int [M];
    static int [] ne = new int [M];
    static int idx = 0;

    static void add(int [] h,int a,int b){
        e[idx] = b;ne[idx] = h[a];h[a] = idx++;
    }

    // flag = 0表示铁路，flag = 1表示公路
    static int spfa(int [] h,int flag){
        if(flag==0&&g[1][n]==1) return 1;
        if(flag==1&&g[1][n]!=1) return 1;

        Arrays.fill(d, INF);
        use = new boolean[N];
        int[] q = new int[N];// 队列
        int hh = 0, tt = 0;// hh表示队头，tt表示队尾

        q[tt++] = 1;use[1] = true;d[1] = 0;

        while(hh != tt){
            int node = q[hh++];
            use[node] = false;
            if(hh==N) hh = 0;

            for(int idxx = h[node];idxx != -1;idxx = ne[idxx]){
                int nodee = e[idxx];
                if(d[nodee] > d[node]+1){
                    d[nodee] = d[node]+1;
                    if(!use[nodee]){
                        q[tt++] = nodee;
                        use[nodee] = true;
                        if(tt==N) tt = 0;
                    }
                }
            }
        }
        return d[n];
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();m = sc.nextInt();
        Arrays.fill(h0, -1);
        Arrays.fill(h1, -1);

        for(int i = 1;i <= m;i++){
            int a = sc.nextInt();int b = sc.nextInt();
            g[a][b]=g[b][a] = 1;
            add(h0,a,b);add(h0,b,a);
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j < i;j++){
                if(g[i][j]!=1){
                    add(h1, i, j);add(h1,j,i);
                }
            }
        }

        // 0表示铁路，1表示公路
        int result = Math.max(spfa(h0,0), spfa(h1,1));
        if(result>=INF) result = -1;
        System.out.println(result);
    }
}

算法3 floyd算法

// floyd算法
import java.util.*;
public class Main {
    static int N = 410;
    static int n;
    static int [][] dg = new int[N][N];
    static int [][] dt = new int[N][N];
    static int INF = 0x3f3f;

    static int floyd(int[][]d){
        if(d[1][n]==1) return 1;
        for(int k = 1;k <= n;k++){
            for(int i = 1;i <= n;i++){
                for(int j = 1;j <= n;j++){
                    d[i][j] = Math.min(d[i][j],d[i][k]+d[k][j]);
                }
            }
        }
        return d[1][n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();int m = sc.nextInt();
        for(int i = 1;i <= n;i++){
            Arrays.fill(dt[i], INF);
            Arrays.fill(dg[i], INF);
        }

        for(int i = 0;i < m;i++){
            int a = sc.nextInt();int b = sc.nextInt();
            dt[a][b]=dt[b][a] = 1;
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                if(dt[i][j]!=1) dg[i][j] = 1; 
            }
        }

        int result = Math.max(floyd(dt),floyd(dg));
        if(result >= INF) System.out.println(-1);
        else System.out.println(result);

    }
}