归并排序

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 100005;
    static int n, m, k;
    static int[] a = new int[N];
    static int[] t = new int[N];
    public static void main(String[] args) throws Exception {
        //Scanner sc = new Scanner(System.in);
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = bf.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        s = bf.readLine().split(" ");
        for(int i = 1; i <= n; i ++)
        {
            a[i] = Integer.parseInt(s[i - 1]);
        }

        merge_sort(1, n);

        for(int i = 1; i <= n; i ++)
        {
            bw.write(a[i] + " ");
        }
        bw.flush();
    }

   public static void merge_sort(int l, int r)
   {
       if(l >= r) return;
       int mid = (l + r) >> 1;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r)
        {
            if(a[i] < a[j])
            {
                t[k ++] = a[i ++];
            }
            else t[k ++] = a[j ++];
        }

        while(i <= mid) t[k ++] = a[i ++];
        while(j <= r) t[k ++] = a[j ++];

        for(int o = l, p = 0; o <= r; o ++, p ++) a[o] = t[p];
   }
}

前缀和

一维

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 100005;
    static int[] a = new int[N];
    static int[] s = new int[N];
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            a[i] = sc.nextInt();
            s[i] = s[i - 1] + a[i];
        }

        while(m -- > 0)
        {
            int l = sc.nextInt(), r = sc.nextInt();
            System.out.println(s[r] - s[l - 1]);
        }
}

}

二维

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 1005;
    static int[][] a = new int[N][N];
    static int[][] s = new int[N][N];
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                a[i][j] = sc.nextInt();
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
            }
        while(q -- > 0)
        {
            int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt();
            System.out.printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);

        }

}
}

差分

一维

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 100100;
    static int[] d = new int[N];
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            int x;
            x = sc.nextInt();
            cf(i, i, x);
        }
        while(q -- > 0)
        {
            int l = sc.nextInt(), r = sc.nextInt(), c = sc.nextInt();
            cf(l, r, c);
        }
        for(int i = 1; i <= n; i ++) d[i] += d[i - 1];

        for(int i = 1; i <= n; i ++)
        {
            System.out.printf("%d ", d[i]);
        }
}
    public static void cf(int l, int r, int w)
    {
        d[l] += w;
        d[r + 1] -= w;
    }
}

二维

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 1010;
    static int[][] d = new int[N][N];
    public static void main(String[] args) throws Exception {
        //Scanner sc = new Scanner(System.in);
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] ss = bf.readLine().split(" ");
        int n = Integer.parseInt(ss[0]);
        int m = Integer.parseInt(ss[1]);
        int q = Integer.parseInt(ss[2]);


        for(int i = 1; i <= n; i ++)
        {
             String[] s = bf.readLine().split(" "); 
            for(int j = 1; j <= m; j ++)
            {
                int x = Integer.parseInt(s[j - 1]);
                cf(i, j, i, j, x);
            }
        }
        while(q -- > 0)
        {
            ss = bf.readLine().split(" ");
            int x1 = Integer.parseInt(ss[0]), y1 = Integer.parseInt(ss[1]), x2 = Integer.parseInt(ss[2]), y2 = Integer.parseInt(ss[3]);
            int w = Integer.parseInt(ss[4]);
            cf(x1, y1, x2, y2, w);
        }
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + d[i][j];

        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= m; j ++)
                bw.write(d[i][j] + " ");

            bw.write("\n");
        }
        bw.flush();
}
    public static void cf(int x1, int y1, int x2, int y2, int w)
    {
         d[x1][y1] += w;
         d[x2 + 1][y1] -= w;
         d[x1][y2 + 1] -= w;
         d[x2 + 1][y2 + 1] += w;
    }
}

区间合并

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 100010, MOD = 1000000007;

        static class PII implements Comparable<PII> //相当于定义了一个C++里面的pair二元组
        {
            int x, y;
            public PII(int x, int y)
            {
                this.x = x;
                this.y = y;
            }

            public int compareTo(PII v)
            {
                return x - v.x;
            }
        }
        public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
           int n = sc.nextInt();
           List<PII> list = new ArrayList<>();
           for(int i = 1; i <= n; i ++)
           {
               int l = sc.nextInt();
               int r = sc.nextInt();
               list.add(new PII(l, r));
           }
           Collections.sort(list); //用collections来进行排序
           int res = 0;
           int st = (int)-2e9; //定义为负无穷的方法
           int ed = (int)-2e9;
           for(int i = 0; i < list.size(); i ++)
           {
               PII t = list.get(i);
               if(st == (int)-2e9 || ed < t.x)
               {
                   st = t.x;
                   ed = t.y;
                   res ++;
               }
               else ed = Math.max(ed, t.y);
           }
           System.out.println(res);
}
}

单调栈

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 100010, MOD = 1000000007;
        static int[] stk = new int[N]; //单调栈中存储的是下标
        static int[] a = new int[N];
        static int[] l = new int[N];//存储答案的数组
        static int top; //模拟栈的栈顶指针
        public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            for(int i = 1; i <= n; i ++) 
               a[i] = sc.nextInt();

            for(int i = 1; i <= n; i ++)
            {
                while(top > 0 && a[stk[top]] >= a[i]) top --;
                if(top > 0) l[i] = stk[top];
                else l[i] = -1;

                stk[++ top] = i;
            }
            for(int i = 1; i <= n; i ++) 
                if(l[i] == -1)System.out.printf("%d ", l[i]);
                else System.out.printf("%d ", a[l[i]]);
}
}

单调队列

维护一个滑动窗口，确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1000010, MOD = 1000000007;
        static int[] q = new int[N]; //单调队列中存储的是下标
        static int[] a = new int[N];
        static int tt, hh = 1; //模拟队列的指针，tt为队尾，hh为队头
        public static void main(String[] args) throws Exception {
            //Scanner sc = new Scanner(System.in);
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            String[] s = bf.readLine().split(" ");
            int n = Integer.parseInt(s[0]);
            int k = Integer.parseInt(s[1]);
            s = bf.readLine().split(" ");
            for(int i = 1; i <= n; i ++)
            {
                a[i] = Integer.parseInt(s[i - 1]);
            }

            //先求最小值
            for(int i = 1; i <= n; i ++)
            {
                while(tt >= hh && q[hh] < i - k + 1) hh ++; //判断队头合法性
                while(tt >= hh && a[q[tt]] >= a[i]) tt --; //判断队尾合法性
                q[++ tt] = i;

                if(i >= k) bw.write(a[q[hh]] + " ");
            }

            bw.write("\n");

            tt = 0;
            hh = 1;
            //求最大值
            for(int i = 1; i <= n; i ++)
            {
                while(tt >= hh && q[hh] < i - k + 1) hh ++;
                while(tt >= hh && a[q[tt]] <= a[i]) tt --;
                q[++ tt] = i;

                if(i >= k) bw.write(a[q[hh]] + " ");
            }
            bw.flush();
}
}

KMP字符串匹配

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1000010, MOD = 1000000007;
        static int[] ne = new int[N];
        public static void main(String[] args) throws Exception {
            //Scanner sc = new Scanner(System.in);
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = Integer.parseInt(bf.readLine());
            String p = " " + bf.readLine(); //读入p串保证下标从1开始
            int m = Integer.parseInt(bf.readLine());
            String s = " " + bf.readLine(); 

            //初始化ne数组   
            for(int i = 2, j = 0; i <= n; i ++)
            {
                while(j > 0 && p.charAt(i) != p.charAt(j + 1)) j = ne[j];
                if(p.charAt(i) == p.charAt(j + 1)) j ++;
                ne[i] = j;
            }

            //开始匹配 
            for(int i = 1, j = 0; i <= m; i ++)
            {
                while(j > 0 && s.charAt(i) != p.charAt(j + 1)) j = ne[j];
                if(s.charAt(i) == p.charAt(j + 1)) j ++;
                if(j == n)
                {
                    bw.write(i - n + " ");
                    j = ne[j];
                }
            }
            bw.flush();
}
}

并查集

朴素版本

package test;
import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 100010, MOD = 1000000007;
        static int[] p = new int[N];
        public static int find(int x)
        {
            if(x != p[x]) p[x] = find(p[x]);
            return p[x];
        }

        public static void merge(int x, int y)
        {
            int fx = find(x);
            int fy = find(y);
            p[fx] = fy;
        }
        public static void main(String[] args) throws Exception {
            //Scanner sc = new Scanner(System.in);
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            String[] s = bf.readLine().split(" ");
            int n = Integer.parseInt(s[0]);
            int m = Integer.parseInt(s[1]);
            for(int i = 1; i <= n; i ++) p[i] = i; //初始化并查集数组
            while(m -- > 0)
            {
                s = bf.readLine().split(" ");
                int x = Integer.parseInt(s[1]);
                int y = Integer.parseInt(s[2]);
                if(s[0].equals("Q"))
                {
                    if(find(x) == find(y)) bw.write("Yes" + "\n");
                    else bw.write("No" + "\n");
                }
                else
                {
                    merge(x, y);
                }
            }
            bw.flush();
}
}

维护节点数量的并查集

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 100010, MOD = 998244353;
        static int n, m;
        static int[] p = new int[N]; //并查集数组
        static int[] sz = new int[N]; // 维护集合的大小的数组
        public static int find(int x)
        {
            if(x != p[x]) p[x] = find(p[x]);
            return p[x];
        }
        public static void main(String[] args) throws Exception {
            //Scanner sc = new Scanner(System.in);
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            String[] s = bf.readLine().split(" ");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            for(int i = 1; i <= n; i ++)
            {
                p[i] = i;
                sz[i] = 1;
            }

            for(int i = 1; i <= m; i ++)
            {
                s = bf.readLine().split(" ");
                if(s[0].equals("C"))
                {
                    int x = Integer.parseInt(s[1]);
                    int y = Integer.parseInt(s[2]);
                    int fx = find(x);
                    int fy = find(y);
                    if(fx != fy)
                    {
                        p[fx] = fy;
                        sz[fy] += sz[fx];
                    }

                }
                else if(s[0].equals("Q1"))
                {
                    int x = Integer.parseInt(s[1]);
                    int y = Integer.parseInt(s[2]);
                    if(find(x) == find(y)) bw.write("Yes" + "\n");
                    else bw.write("No" + "\n");
                }
                else
                {
                    int x = Integer.parseInt(s[1]);
                    int fx = find(x);
                    bw.write(sz[fx] + "\n");
                }
            }
            bw.flush();
}
}

字符串Hash

package test;
import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 100010, p = 131;
        static final long Q = Long.MAX_VALUE;
        static long[] P = new long[N];
        static long[] h = new long[N];

        public static long getans(int l, int r)
        {
            return h[r] - h[l - 1] * P[r - l + 1];
        }
        public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();
            String str = " " + sc.next(); //让字符下标从1开始
            P[0] = 1;
            for(int i = 1; i <= n; i ++)
            {
                P[i] = P[i - 1] * p % Q;
                h[i] = h[i - 1] * p % Q + str.charAt(i);
            }

            while(m -- > 0)
            {
                int l1, r1, l2, r2;
                l1 = sc.nextInt();
                r1 = sc.nextInt();
                l2 = sc.nextInt();
                r2 = sc.nextInt();
                if(getans(l1, r1) == getans(l2, r2)) System.out.println("Yes");
                else System.out.println("No");
            }
}
}

BFS

package test;
import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 110, p = 131;
        static final long Q = Long.MAX_VALUE;
        static int[][] a = new int[N][N];
        static int[][] dis = new int[N][N];
        static int n, m;
        static class PII
        {
            int x, y;
            public PII(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
        }
        public static int bfs()
        {
            Queue<PII> q = new LinkedList<>();
            int[] dx = {0, 1, 0, -1};
            int[] dy = {1, 0, -1, 0};
            q.add(new PII(1, 1));
            while(!q.isEmpty())
            {
                PII t = q.remove();
                for(int i = 0; i < 4; i ++)
                {
                    int tx = t.x + dx[i];
                    int ty = t.y + dy[i];

                    if(tx < 1 || tx > n || ty < 1 || ty > m || dis[n][m] != 0 || a[tx][ty] == 1) continue;

                    //if(tx == n && ty == m) return dis[t.x][t.y] + 1;

                    dis[tx][ty] = dis[t.x][t.y] + 1;
                    q.add(new PII(tx, ty));
                }
            }
            return dis[n][m];

        }
        public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
             n = sc.nextInt();
             m = sc.nextInt();
            for(int i = 1; i <= n; i ++)
                for(int j = 1; j <= n; j ++)
                {
                    a[i][j] = sc.nextInt();
                }

            System.out.println(bfs());
}
}

求欧拉函数

package test;
import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 110, p = 131;
        static final long Q = Long.MAX_VALUE;

        public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            while(n -- > 0)
            {
                int x = sc.nextInt();

                int res = x;
                for(int i = 2; i <= x / i; i ++)
                {
                    if(x % i == 0)
                    {
                        while(x % i == 0) x /= i;
                        res = res / i * (i - 1);  //先乘后除，防止answer出错
                    }

                }
                if(x > 1) res = res / x * (x - 1);
                System.out.println(res);
            }
}
}

树和图的深度优先搜索（DFS）

算法基础课：求树的重心

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 100010, p = 131;
        static int[] h = new int[N];
        static int[] e = new int[N * 2]; 
        static int[] ne = new int[N * 2]; 
      //h数组存各个节点的链表头，e存当前编号下的节点值，ne存当前编号下一个节点的编号（无向边需要将数组开大两倍） 
        static int n, idx;
        static int ans = N;
        static boolean[] st = new boolean[N];
        public static void add(int a, int b)
        {
            e[idx] = b;
            ne[idx] = h[a];
            h[a] = idx ++;
        }

        public static int dfs(int u)
        {
            int sum = 1, res = 0;
            st[u] = true;
            for(int i = h[u]; i != -1; i = ne[i])
            {
                int j = e[i];
                if(!st[j])
                {
                    int s = dfs(j);
                    sum += s;
                    res = Math.max(res, s);
                }
            }
            res = Math.max(res, n - sum);
            ans = Math.min(res, ans);
            return sum;
        }
        public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            n = sc.nextInt();
            Arrays.fill(h, -1);
            for(int i = 1; i <= n - 1; i ++)
            {
                int a, b;
                a = sc.nextInt();
                b = sc.nextInt();
                add(a, b);
                add(b, a);
            }
            dfs(1);
            System.out.println(ans);

}
}

树和图的宽度优先搜索（BFS）

例题：图中点的层次

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 100010, p = 131;
        static int[] h = new int[N];
        static int[] d = new int[N];
        static int[] e = new int[N * 2]; 
        static int[] ne = new int[N * 2]; 
      //h数组存各个节点的链表头，e存当前编号下的节点值，ne存当前编号下一个节点的编号（无向边需要将数组开大两倍） 
        static int n, m, idx;
        static int ans = N;
        static boolean[] st = new boolean[N];
        public static void add(int a, int b)
        {
            e[idx] = b;
            ne[idx] = h[a];
            h[a] = idx ++;
        }

        public static int bfs()
        {
            Queue<Integer> q = new LinkedList<>();
            q.add(1);
            d[1] = 0;
            while(q.size() > 0)
            {
                int t = q.remove();
                for(int i = h[t]; i != -1; i = ne[i])
                {
                    int j = e[i];
                    if(d[j] == -1)
                    {
                        d[j] = d[t] + 1;
                        q.add(j);
                    }
                }
            }
            return d[n];
        }
        public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            n = sc.nextInt();
            m = sc.nextInt();
            Arrays.fill(h, -1);
            Arrays.fill(d, -1);
            for(int i = 1; i <= m; i ++)
            {
                int a, b;
                a = sc.nextInt();
                b = sc.nextInt();
                add(a, b);
            }

            System.out.println(bfs());

}
}

堆优化版dijkstra算法

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 150001;
        static final int inf = 0x3f3f3f3f;
        static int[] h = new int[N];
        static int[] e = new int[N];
        static int[] ne = new int[N];
        static int[] w = new int[N];
        static int[] dist = new int[N];
        static boolean[] st = new boolean[N];
        static int idx, n, m;
        static class pii implements Comparable<pii>
        {
            int d, num;
            public pii(int d, int num)
            {
                this.d = d;
                this.num = num;
            }

            public int compareTo(pii v)
            {
                return d - v.d;
            }
        }
        public static void add(int a, int b, int c)
        {
            e[idx] = b;
            w[idx] = c;
            ne[idx] = h[a];
            h[a] = idx ++;
        }

        public static int dijkstra()
        {
            Arrays.fill(dist, inf);

            Queue<pii> pq = new PriorityQueue<>();

            dist[1] = 0;
            pq.add(new pii(0, 1));
            while(pq.size() > 0)
            {
                pii t = pq.remove();
                int u = t.num;
                if(st[u] == true) continue;
                st[u] = true;

                for(int i = h[u]; i != -1; i = ne[i])
                {
                    int j = e[i];

                    if(dist[j] > dist[u] + w[i])
                    {
                        dist[j] = dist[u] + w[i];
                        pq.add(new pii(dist[j], j));
                    }

                }
            }
            return dist[n];
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            n = sc.nextInt();
            m = sc.nextInt();
            Arrays.fill(h, -1);
            for(int i = 1; i <= m; i ++)
            {
                int a, b, w;
                a = sc.nextInt();
                b = sc.nextInt();
                w = sc.nextInt();
                add(a, b, w);
            }

            int res = dijkstra();
            if(res == inf) System.out.println(-1);
            else System.out.println(res);
        }     
}

floyd求最短路

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 210;
        static final int inf = 0x3f3f3f3f;
        static int n, m, k;
        static int[][] d = new int[N][N];

        public static void floyd()
        {
            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]);
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            n = sc.nextInt();
            m = sc.nextInt();
            k = sc.nextInt();

            for(int i = 1; i <= n; i ++)
                for(int j = 1; j <= n; j ++)
                    if(i == j) d[i][j] = 0; //可能存在询问自身到自身的距离，所以需要存0
                    else d[i][j] = inf;//然后其他都可以存成INF最大值

            while(m -- > 0)
            {
                int a, b, w;
                a = sc.nextInt();
                b = sc.nextInt();
                w = sc.nextInt();
                d[a][b] = Math.min(d[a][b], w); //这里可能存在重边，取最小的边
            }

            floyd();

            while(k -- > 0)
            {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int res = d[x][y];
                //这里可能最后到不了目标点，但是可能路径上面存在负权边，然后将目标点更新了，所以不是到底== INF
                if(res > inf / 2) System.out.println("impossible");
                else System.out.println(res);
            }
        }     
}

最小生成树kruskal算法

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 200010;
        static final int inf = 0x3f3f3f3f;
        static int n, m;
        static int[] p = new int[N];
        static Edge[] edge = new Edge[N]; 
        static class Edge implements Comparable<Edge>{
            int a, b, w;

            public Edge(int a, int b, int w)
            {
                this.a = a;
                this.b = b;
                this.w = w;
            }

            public int compareTo(Edge v)
            {
                return w - v.w;
            }
        }
        public static int find(int x)
        {
            if(p[x] != x) p[x] = find(p[x]);
            return p[x];
        }

        public static void kruskal()
        {
            int res = 0;
            int cnt = 0;
            for(int i = 1; i <= m; i ++)
            {
                int x = edge[i].a;
                int y = edge[i].b;
                int fx = find(x), fy = find(y);
                if(fx != fy)
                {
                    p[fx] = fy;
                    res += edge[i].w;
                    cnt ++;
                }
            }

            if(cnt != n - 1) System.out.println("impossible");
            else System.out.println(res);
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            n = sc.nextInt();
            m = sc.nextInt();
            //初始化并查集
            for(int i = 1; i <= n; i ++) p[i] = i;

            for(int i = 1; i <= m; i ++)
            {
                int a, b, w;
                a = sc.nextInt();
                b = sc.nextInt();
                w = sc.nextInt();
                edge[i] = new Edge(a, b, w);
            }

            Arrays.sort(edge, 1, 1 + m);

            kruskal();
        }     
}