头像

栗子ing

广东科学技术职业学院




离线:7小时前


最近来访(1429)
用户头像
白月光L
用户头像
心向
用户头像
李京泽
用户头像
帅到被人砍
用户头像
怪咖_4
用户头像
ahh.
用户头像
希尔维亚
用户头像
千秋Q
用户头像
ZOSJ
用户头像
梦溪
用户头像
WearSpring
用户头像
不拼一把怎么行
用户头像
Cabbage_wa
用户头像
轩缈喵不会喵喵喵
用户头像
周赛三题必WA
用户头像
FunGuy
用户头像
MJgopher
用户头像
猫君勉乎哉
用户头像
暗夜星光111
用户头像
Self7


栗子ing
9小时前

floyd实现传递闭包

d = g.clone();

for (int k = 0 ; k < n ; k ++ )
    for (int i = 0 ; i < n ; i ++ )
        for (int j = 0 ; j < n ; j ++ )
        if (d[i][k] == 1 && d[k][j] == 1)
            d[i][j] = 1;
        //d[i][j] |= (d[i][k] & d[k][j]);

思路:
1、如果有矛盾,表示有传递闭包d[i][i] == 1
2、如果有唯一确定的关系,表示对于任意i != j,都存在d[i][j] == 1 / d[j][i] == 1
3、没有矛盾,并且没有唯一确定的关系

代码实现

import java.util.*;
public class Main{
    static int N = 26;
    static int n,m;
    static int[][] g = new int[N][N];//g表示两个数之间有没有边
    static int[][] d = new int[N][N];//d表示传递闭包
    static boolean[] st = new boolean[N];//输出时候用到的判重数组

    //folyd实现传递闭包
    public static void floyd(){
        //进行传递闭包前的初始化,将g拷贝给d
        d = g.clone();

        for (int k = 0 ; k < n ; k ++ )
            for (int i = 0 ; i < n ; i ++ )
                for (int j = 0 ; j < n ; j ++ )
                    if (d[i][k] == 1 && d[k][j] == 1)
                        d[i][j] = 1;

                    //d[i][j] |= (d[i][k] & d[k][j]);
    }
    //判断所有字母关系的情况
    public static int check(){
        //判断所有数,如果有相同的一个数之间有边,那么就表示有矛盾,返回2
        for (int i = 0 ; i < n ; i ++ )
            if (d[i][i] == 1)
                return 2;

        //如果其中任意两个不相等的数之间没有边,那么说明还没有确定好关系,返回0
        for (int i = 0 ; i < n ; i ++ )
            for (int j = 0 ; j < i ; j ++ )
                if (d[i][j] == 0 && d[j][i] == 0)
                    return 0;

        //能够执行到这里,表示已经确定好关系了,直接返回1
        return 1;
    }

    //输出函数,取出最小值
    public static char get_min(){

        //枚举所有数,判断哪些数还没有被输出
        for (int i = 0 ; i < n; i ++ ){
            if (!st[i]){ //如果这个数还没有被输出的话
                boolean flag = true; 
                //枚举所有数,如果这个点没有被标记过,并且,j指向i是1,
                //表示有数比i小,所以flag标记成false,然后break
                for (int j = 0 ; j < n ; j ++ ){
                    if (!st[j] && d[j][i] == 1){
                        flag = false;
                        break;
                    }
                }
                //如果flag是true表示没有点指向i,那么i是最小值,那么返回i,记得转化成char
                if (flag){
                    st[i] = true;
                    return (char)(i + 'A');
                }
            }
        }
        return ' ';   //不执行
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while (true){
            n = scan.nextInt();
            m = scan.nextInt();
            if (n == 0 && m == 0) break;
            //多组测试数据,每一次都进行初始化,防止干扰
            for (int i = 0 ; i < N ; i ++ ) Arrays.fill(g[i],0);

            //type: 0表示不能确定关系;1表示有矛盾;2表示有唯一确定的关系
            //t表示判断了几条之后才确定的
            int type = 0,t = 0;

            //输入m组数据
            for (int i = 1 ; i <= m ; i ++ ){
                String str = scan.next();
                int a = str.charAt(0) - 'A';
                int b = str.charAt(2) - 'A';
                //type如果是0,表示现在还没有确定关系,那么就继续执行
                if (type == 0){
                    g[a][b] = 1; //a与b之间有一条边
                    floyd(); //传递闭包
                    type = check(); //判断一下现在的关系
                    if (type != 0) t = i; //如果当前的关系已经找到,那么将当前执行的次数i赋值给t
                }
            }
            //如果type等于0,说明没有确定关系,直接输出
            if (type == 0) System.out.println("Sorted sequence cannot be determined.");
            //如果type等于2,表示有矛盾,输出相关枚举次数t
            else if (type == 2) System.out.printf("Inconsistency found after %d relations.\n",t);
            //最后如果type等于1,表示没有矛盾,有唯一确定的关系
            else {
                //多组测试数据,每一次都进行清空
                Arrays.fill(st,false);
                //先输出前缀
                System.out.printf("Sorted sequence determined after %d relations: ",t);
                //判断一下所有数,每一次输出最小值
                for (int i = 0 ; i < n ; i ++ )  System.out.print(get_min());
                System.out.printf(".\n");
            }
        }
    }
}


活动打卡代码 AcWing 343. 排序

栗子ing
9小时前

floyd实现传递闭包

d = g.clone();

for (int k = 0 ; k < n ; k ++ )
    for (int i = 0 ; i < n ; i ++ )
        for (int j = 0 ; j < n ; j ++ )
        if (d[i][k] == 1 && d[k][j] == 1)
            d[i][j] = 1;
        //d[i][j] |= (d[i][k] & d[k][j]);

思路:
1、如果有矛盾,表示有传递闭包d[i][i] == 1
2、如果有唯一确定的关系,表示对于任意i != j,都存在d[i][j] == 1 / d[j][i] == 1
3、没有矛盾,并且没有唯一确定的关系

代码实现

import java.util.*;
public class Main{
    static int N = 26;
    static int n,m;
    static int[][] g = new int[N][N];//g表示两个数之间有没有边
    static int[][] d = new int[N][N];//d表示传递闭包
    static boolean[] st = new boolean[N];//输出时候用到的判重数组

    //folyd实现传递闭包
    public static void floyd(){
        //进行传递闭包前的初始化,将g拷贝给d
        d = g.clone();

        for (int k = 0 ; k < n ; k ++ )
            for (int i = 0 ; i < n ; i ++ )
                for (int j = 0 ; j < n ; j ++ )
                    if (d[i][k] == 1 && d[k][j] == 1)
                        d[i][j] = 1;

                    //d[i][j] |= (d[i][k] & d[k][j]);
    }
    //判断所有字母关系的情况
    public static int check(){
        //判断所有数,如果有相同的一个数之间有边,那么就表示有矛盾,返回2
        for (int i = 0 ; i < n ; i ++ )
            if (d[i][i] == 1)
                return 2;

        //如果其中任意两个不相等的数之间没有边,那么说明还没有确定好关系,返回0
        for (int i = 0 ; i < n ; i ++ )
            for (int j = 0 ; j < i ; j ++ )
                if (d[i][j] == 0 && d[j][i] == 0)
                    return 0;

        //能够执行到这里,表示已经确定好关系了,直接返回1
        return 1;
    }

    //输出函数,取出最小值
    public static char get_min(){

        //枚举所有数,判断哪些数还没有被输出
        for (int i = 0 ; i < n; i ++ ){
            if (!st[i]){ //如果这个数还没有被输出的话
                boolean flag = true; 
                //枚举所有数,如果这个点没有被标记过,并且,j指向i是1,
                //表示有数比i小,所以flag标记成false,然后break
                for (int j = 0 ; j < n ; j ++ ){
                    if (!st[j] && d[j][i] == 1){
                        flag = false;
                        break;
                    }
                }
                //如果flag是true表示没有点指向i,那么i是最小值,那么返回i,记得转化成char
                if (flag){
                    st[i] = true;
                    return (char)(i + 'A');
                }
            }
        }
        return ' ';   //不执行
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while (true){
            n = scan.nextInt();
            m = scan.nextInt();
            if (n == 0 && m == 0) break;
            //多组测试数据,每一次都进行初始化,防止干扰
            for (int i = 0 ; i < N ; i ++ ) Arrays.fill(g[i],0);

            //type: 0表示不能确定关系;1表示有矛盾;2表示有唯一确定的关系
            //t表示判断了几条之后才确定的
            int type = 0,t = 0;

            //输入m组数据
            for (int i = 1 ; i <= m ; i ++ ){
                String str = scan.next();
                int a = str.charAt(0) - 'A';
                int b = str.charAt(2) - 'A';
                //type如果是0,表示现在还没有确定关系,那么就继续执行
                if (type == 0){
                    g[a][b] = 1; //a与b之间有一条边
                    floyd(); //传递闭包
                    type = check(); //判断一下现在的关系
                    if (type != 0) t = i; //如果当前的关系已经找到,那么将当前执行的次数i赋值给t
                }
            }
            //如果type等于0,说明没有确定关系,直接输出
            if (type == 0) System.out.println("Sorted sequence cannot be determined.");
            //如果type等于2,表示有矛盾,输出相关枚举次数t
            else if (type == 2) System.out.printf("Inconsistency found after %d relations.\n",t);
            //最后如果type等于1,表示没有矛盾,有唯一确定的关系
            else {
                //多组测试数据,每一次都进行清空
                Arrays.fill(st,false);
                //先输出前缀
                System.out.printf("Sorted sequence determined after %d relations: ",t);
                //判断一下所有数,每一次输出最小值
                for (int i = 0 ; i < n ; i ++ )  System.out.print(get_min());
                System.out.printf(".\n");
            }
        }
    }
}



栗子ing
18小时前

Floyd 相关题解
https://www.acwing.com/activity/content/code/content/2121530/
跟做阅读理解一样,没看懂之前确实迷糊

import java.util.*;
public class Main{
    static int N = 155,INF = (int)1e20;
    static int n;
    static PII[] q = new PII[N];
    static char[][] g = new char[N][N];
    static double[][] dist = new double[N][N];
    static double[] maxd = new double[N];

    //获取两点之间的欧几里得距离公式
    public static double get_dist(PII i,PII j){
        int dx = i.x - j.x, dy = i.y - j.y;
        //根号下  横坐标之差的平方 + 纵坐标之差的平方
        return (double)Math.sqrt(dx * dx + dy * dy);
    }

    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 ++ )
                    dist[i][j] = Math.min(dist[i][j],dist[i][k] + dist[k][j]);
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        //首先输入的是每一个牧区编号对应的坐标
        //例如i = 1时,1号牧区的坐标是(x,y),存到pair里面
        for (int i = 1 ; i <= n ; i ++ ){
            int x = scan.nextInt();
            int y = scan.nextInt();
            q[i] = new PII(x,y);
        }
        //加下来是一个01矩阵,表示两个牧区编号,坐标表示编号,之间有没有边
        for (int i = 1 ; i <= n ; i ++ ){
            String s = scan.next();
            for (int j = 1 ; j <= n ; j ++ )
                g[i][j] = s.charAt(j - 1);
        }        

        //初始化,如果两个点直接有边,那么就获取他们两个的欧几里得距离,
        //没有边就初始化成INF
        for (int i = 1 ; i <= n ; i ++ )
            for (int j = 1 ; j <= n ; j ++ )
                if (i != j)
                    if (g[i][j] == '1') dist[i][j] = get_dist(q[i],q[j]);
                    else dist[i][j] = INF;

        //首先做一遍folyd算法,将所有点的最短距离求出来
        floyd();        

        //求出每个牧区的连通的牧区中的最长距离
        for (int i = 1 ; i <= n ; i ++ ) 
            for (int j = 1 ; j <= n ; j ++ )
                if (dist[i][j] < INF)
                    maxd[i] = Math.max(maxd[i],dist[i][j]);

        //res1表示所有牧区的最长距离的最大值,这个就是我们题目求的直径
        double res1 = 0;
        for (int i = 1 ; i <= n ; i ++ ) res1 = Math.max(res1,maxd[i]);

        //res2枚举所有不连通的牧场,然后依次连接所有的点,找到连接最短的那条,记录下来
        double res2 = INF;
        for (int i = 1 ; i <= n ; i ++ )
            for (int j = 1 ; j <= n ; j ++ )
                if (dist[i][j] >= INF)
                    res2 = Math.min(res2,get_dist(q[i],q[j]) + maxd[i] + maxd[j]);

        //最后res1可能不是res2所连接的那条路径的牧场,
        //但是有可能res1没有连的路径都比我们连接的路径大。

        System.out.printf("%.6f",Math.max(res1,res2));//所以两个数取一个max
    }
}
class PII{
    int x,y;
    public PII(int x,int y){
        this.x = x;
        this.y = y;
    }
}


活动打卡代码 AcWing 1125. 牛的旅行

栗子ing
18小时前

Floyd 相关题解
https://www.acwing.com/activity/content/code/content/2121530/
跟做阅读理解一样,没看懂之前确实迷糊

import java.util.*;
public class Main{
    static int N = 155,INF = (int)1e20;
    static int n;
    static PII[] q = new PII[N];
    static char[][] g = new char[N][N];
    static double[][] dist = new double[N][N];
    static double[] maxd = new double[N];

    //获取两点之间的欧几里得距离公式
    public static double get_dist(PII i,PII j){
        int dx = i.x - j.x, dy = i.y - j.y;
        //根号下  横坐标之差的平方 + 纵坐标之差的平方
        return (double)Math.sqrt(dx * dx + dy * dy);
    }

    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 ++ )
                    dist[i][j] = Math.min(dist[i][j],dist[i][k] + dist[k][j]);
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        //首先输入的是每一个牧区编号对应的坐标
        //例如i = 1时,1号牧区的坐标是(x,y),存到pair里面
        for (int i = 1 ; i <= n ; i ++ ){
            int x = scan.nextInt();
            int y = scan.nextInt();
            q[i] = new PII(x,y);
        }
        //加下来是一个01矩阵,表示两个牧区编号,坐标表示编号,之间有没有边
        for (int i = 1 ; i <= n ; i ++ ){
            String s = scan.next();
            for (int j = 1 ; j <= n ; j ++ )
                g[i][j] = s.charAt(j - 1);
        }        

        //初始化,如果两个点直接有边,那么就获取他们两个的欧几里得距离,
        //没有边就初始化成INF
        for (int i = 1 ; i <= n ; i ++ )
            for (int j = 1 ; j <= n ; j ++ )
                if (i != j)
                    if (g[i][j] == '1') dist[i][j] = get_dist(q[i],q[j]);
                    else dist[i][j] = INF;

        //首先做一遍folyd算法,将所有点的最短距离求出来
        floyd();        

        //求出每个牧区的连通的牧区中的最长距离
        for (int i = 1 ; i <= n ; i ++ ) 
            for (int j = 1 ; j <= n ; j ++ )
                if (dist[i][j] < INF)
                    maxd[i] = Math.max(maxd[i],dist[i][j]);

        //res1表示所有牧区的最长距离的最大值,这个就是我们题目求的直径
        double res1 = 0;
        for (int i = 1 ; i <= n ; i ++ ) res1 = Math.max(res1,maxd[i]);

        //res2枚举所有不连通的牧场,然后依次连接所有的点,找到连接最短的那条,记录下来
        double res2 = INF;
        for (int i = 1 ; i <= n ; i ++ )
            for (int j = 1 ; j <= n ; j ++ )
                if (dist[i][j] >= INF)
                    res2 = Math.min(res2,get_dist(q[i],q[j]) + maxd[i] + maxd[j]);

        //最后res1可能不是res2所连接的那条路径的牧场,
        //但是有可能res1没有连的路径都比我们连接的路径大。

        System.out.printf("%.6f",Math.max(res1,res2));//所以两个数取一个max
    }
}
class PII{
    int x,y;
    public PII(int x,int y){
        this.x = x;
        this.y = y;
    }
}



1、与最短路计数类似,只不过将求最短路的同时,增加了一个求次短路的数量
2、因为次短路最短路一样,都符合拓扑序,所以按照最短路的求解方式次短路同样的方法更新就行了
3、将次短跟最短看成两个不同的点,然后进行更新

import java.util.*;
import java.io.*;
public class Main{
    static int N = 1010, M = 10010, INF = 0x3f3f3f3f;
    static int n,m,S,T,idx;
    static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];
    static int[][] dist = new int[N][2];//d[i][0]表示最短路径,d[i][1]表示次短路径
    static int[][] cnt = new int[N][2];
    static boolean[][] st = new boolean[N][2];

    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(){
        //因为有多组测试数据,所以每次都需要初始化
        for (int i = 0 ; i < N ; i ++ ){
            Arrays.fill(dist[i],INF);
            Arrays.fill(st[i],false);
            Arrays.fill(cnt[i],0);
        }
        //因为起点只有最短,没有此短
        dist[S][0] = 0; //起点最短距离是0
        cnt[S][0] = 1;  //起点最短路径有1条,没有次短距离,所以0条

        PriorityQueue<PII> q = new PriorityQueue<>();
        q.offer(new PII(S,0,0)); //将起点加入队列

        while (q.size() != 0){
            PII t = q.poll();

            int ver = t.ver;  //点
            int type = t.type; //类型0 / 1
            int distence = t.dist; //距离
            int count = cnt[ver][type]; //这个点的对应type的最短路数量或者次短路数量

            if (st[ver][type]) continue; //判断这个点是不是已经加入队列过
            st[ver][type] = true; //出队标记

            //更新所有出边
            //将最短跟次短分别看成一个点,就行了,单独开来,不用将关系看的那么深
            for (int i = h[ver] ; i != -1 ; i = ne[i]){
                int j = e[i];
                //最短路径
                if (dist[j][0] > distence + w[i]){
                    dist[j][1] = dist[j][0];
                    cnt[j][1] = cnt[j][0];
                    q.offer(new PII(j,1,dist[j][1]));
                    dist[j][0] = distence + w[i];
                    cnt[j][0] = count;
                    q.offer(new PII(j,0,dist[j][0]));
                }
                else if (dist[j][0] == distence + w[i]) cnt[j][0] += count;
                //次短路径
                else if (dist[j][1] > distence + w[i]){
                    dist[j][1] = distence + w[i];
                    cnt[j][1] = count;
                    q.offer(new PII(j,1,dist[j][1]));
                }else if (dist[j][1] == distence + w[i]) cnt[j][1] += count;
            }
        }

        //首先res 答案 =  最短路径的条数
        int res = cnt[T][0];
        //如果最短路径 + 1 == 次短路径 
        //那么累加上次短路径的条数
        if (dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];

        return res;//返回答案
    }

    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));

        int cases = Integer.parseInt(bf.readLine());
        while (cases -- > 0){

            String[] s1 = bf.readLine().split(" ");
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);

            idx = 0;
            Arrays.fill(h ,-1);

            while (m -- > 0){
                String[] s2 = bf.readLine().split(" ");
                int a = Integer.parseInt(s2[0]);
                int b = Integer.parseInt(s2[1]);
                int c = Integer.parseInt(s2[2]);
                add(a,b,c);//单向边
            }
            String[] s3 = bf.readLine().split(" ");
            S = Integer.parseInt(s3[0]); //起点
            T = Integer.parseInt(s3[1]);//终点

            wt.println(dijkstra());
            wt.flush();
        }
    }
}
class PII implements Comparable<PII>{
    int ver,type,dist;
    public PII(int ver,int type,int dist){
        this.ver = ver;
        this.type = type;
        this.dist = dist;
    }
    public int compareTo(PII o){
        return Integer.compare(dist,o.dist);
    }
}


活动打卡代码 AcWing 383. 观光

1、与最短路计数类似,只不过将求最短路的同时,增加了一个求次短路的数量
2、因为次短路最短路一样,都符合拓扑序,所以按照最短路的求解方式次短路同样的方法更新就行了
3、将次短跟最短看成两个不同的点,然后进行更新

import java.util.*;
import java.io.*;
public class Main{
    static int N = 1010, M = 10010, INF = 0x3f3f3f3f;
    static int n,m,S,T,idx;
    static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];
    static int[][] dist = new int[N][2];//d[i][0]表示最短路径,d[i][1]表示次短路径
    static int[][] cnt = new int[N][2];
    static boolean[][] st = new boolean[N][2];

    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(){
        //因为有多组测试数据,所以每次都需要初始化
        for (int i = 0 ; i < N ; i ++ ){
            Arrays.fill(dist[i],INF);
            Arrays.fill(st[i],false);
            Arrays.fill(cnt[i],0);
        }
        //因为起点只有最短,没有此短
        dist[S][0] = 0; //起点最短距离是0
        cnt[S][0] = 1;  //起点最短路径有1条,没有次短距离,所以0条

        PriorityQueue<PII> q = new PriorityQueue<>();
        q.offer(new PII(S,0,0)); //将起点加入队列

        while (q.size() != 0){
            PII t = q.poll();

            int ver = t.ver;  //点
            int type = t.type; //类型0 / 1
            int distence = t.dist; //距离
            int count = cnt[ver][type]; //这个点的对应type的最短路数量或者次短路数量

            if (st[ver][type]) continue; //判断这个点是不是已经加入队列过
            st[ver][type] = true; //出队标记

            //更新所有出边
            //将最短跟次短分别看成一个点,就行了,单独开来,不用将关系看的那么深
            for (int i = h[ver] ; i != -1 ; i = ne[i]){
                int j = e[i];
                //最短路径
                if (dist[j][0] > distence + w[i]){
                    dist[j][1] = dist[j][0];
                    cnt[j][1] = cnt[j][0];
                    q.offer(new PII(j,1,dist[j][1]));
                    dist[j][0] = distence + w[i];
                    cnt[j][0] = count;
                    q.offer(new PII(j,0,dist[j][0]));
                }
                else if (dist[j][0] == distence + w[i]) cnt[j][0] += count;
                //次短路径
                else if (dist[j][1] > distence + w[i]){
                    dist[j][1] = distence + w[i];
                    cnt[j][1] = count;
                    q.offer(new PII(j,1,dist[j][1]));
                }else if (dist[j][1] == distence + w[i]) cnt[j][1] += count;
            }
        }

        //首先res 答案 =  最短路径的条数
        int res = cnt[T][0];
        //如果最短路径 + 1 == 次短路径 
        //那么累加上次短路径的条数
        if (dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];

        return res;//返回答案
    }

    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));

        int cases = Integer.parseInt(bf.readLine());
        while (cases -- > 0){

            String[] s1 = bf.readLine().split(" ");
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);

            idx = 0;
            Arrays.fill(h ,-1);

            while (m -- > 0){
                String[] s2 = bf.readLine().split(" ");
                int a = Integer.parseInt(s2[0]);
                int b = Integer.parseInt(s2[1]);
                int c = Integer.parseInt(s2[2]);
                add(a,b,c);//单向边
            }
            String[] s3 = bf.readLine().split(" ");
            S = Integer.parseInt(s3[0]); //起点
            T = Integer.parseInt(s3[1]);//终点

            wt.println(dijkstra());
            wt.flush();
        }
    }
}
class PII implements Comparable<PII>{
    int ver,type,dist;
    public PII(int ver,int type,int dist){
        this.ver = ver;
        this.type = type;
        this.dist = dist;
    }
    public int compareTo(PII o){
        return Integer.compare(dist,o.dist);
    }
}



1、BFS : 每一个点入队一次,出队一次,所以具备拓扑图的性质
2、dijkstra : 每一次都是找到最近的点,也就是最小值,然后出队更新,也是每个点只作为最小值``出队一次,所以具备拓扑图的性质
3、bell_man(spfa) : 每一次出队不一定最小值,所有的点每一次出队更新其他点,后面也还有可能会再次入队,模板中的st[t] = false,每次出队将其记录清空,所以后续不确定会不会再次入队,所以不具备拓扑图的性质

BFS

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

public class Main{
    static int N = 100010,M = 4 * N,INF = 0x3f3f3f3f,mod = 100003;
    static int n,m,idx;
    static int[] h = new int[N],e = new int[M],ne = new int[M];
    static int[] dist = new int[N];//每个点距离起点的最短距离
    static int[] cnt = new int[N];//记录每个点的最短路数
    static boolean[] st = new boolean[N];//判重数组
    static int[] q = new int[N];//bfs队列

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

    public static void bfs(){
        int hh = 0,tt = -1;
        Arrays.fill(dist,INF);
        dist[1] = 0;
        cnt[1] = 1;//1号点自己能够走到自己是一条边

        q[++ tt] = 1;

        while (hh <= tt){
            int t = q[hh ++];

            for (int i = h[t]; i != -1 ; i = ne[i]){
                int j = e[i];
                if (dist[j] > dist[t] + 1){
                    dist[j] = dist[t] + 1;
                    cnt[j] = cnt[t]; //如果t能够更新j,说明能够走到t的所有路径都能够走到j,所以赋值给j
                    if (!st[j]){
                        q[++ tt] = j;
                        st[j] = true;
                    }
                    //如果t走到j的距离等于j的距离,那么就是两条路径相等,t的所有路径都可以走到j,
                    //然后加上h本身自己的数量,两者累加就是所有最短路数量
                }else if (dist[j] == dist[t] + 1) cnt[j] = (cnt[j] + cnt[t]) % mod; 
            }
        }
    }
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        String[] s1 = bf.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);

        Arrays.fill(h,-1);

        while (m -- > 0){
            String[] s2 = bf.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a,b);add(b,a);
        }

        bfs();

        for (int i = 1 ; i <= n ; i ++ ) wt.println(cnt[i]);
        wt.flush();
    }
}


活动打卡代码 AcWing 1134. 最短路计数

1、BFS : 每一个点入队一次,出队一次,所以具备拓扑图的性质
2、dijkstra : 每一次都是找到最近的点,也就是最小值,然后出队更新,也是每个点只作为最小值``出队一次,所以具备拓扑图的性质
3、bell_man(spfa) : 每一次出队不一定最小值,所有的点每一次出队更新其他点,后面也还有可能会再次入队,模板中的st[t] = false,每次出队将其记录清空,所以后续不确定会不会再次入队,所以不具备拓扑图的性质

BFS

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

public class Main{
    static int N = 100010,M = 4 * N,INF = 0x3f3f3f3f,mod = 100003;
    static int n,m,idx;
    static int[] h = new int[N],e = new int[M],ne = new int[M];
    static int[] dist = new int[N];//每个点距离起点的最短距离
    static int[] cnt = new int[N];//记录每个点的最短路数
    static boolean[] st = new boolean[N];//判重数组
    static int[] q = new int[N];//bfs队列

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

    public static void bfs(){
        int hh = 0,tt = -1;
        Arrays.fill(dist,INF);
        dist[1] = 0;
        cnt[1] = 1;//1号点自己能够走到自己是一条边

        q[++ tt] = 1;

        while (hh <= tt){
            int t = q[hh ++];

            for (int i = h[t]; i != -1 ; i = ne[i]){
                int j = e[i];
                if (dist[j] > dist[t] + 1){
                    dist[j] = dist[t] + 1;
                    cnt[j] = cnt[t]; //如果t能够更新j,说明能够走到t的所有路径都能够走到j,所以赋值给j
                    if (!st[j]){
                        q[++ tt] = j;
                        st[j] = true;
                    }
                    //如果t走到j的距离等于j的距离,那么就是两条路径相等,t的所有路径都可以走到j,
                    //然后加上h本身自己的数量,两者累加就是所有最短路数量
                }else if (dist[j] == dist[t] + 1) cnt[j] = (cnt[j] + cnt[t]) % mod; 
            }
        }
    }
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        String[] s1 = bf.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);

        Arrays.fill(h,-1);

        while (m -- > 0){
            String[] s2 = bf.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a,b);add(b,a);
        }

        bfs();

        for (int i = 1 ; i <= n ; i ++ ) wt.println(cnt[i]);
        wt.flush();
    }
}



y总用Set存所有输入的边,这里用的是boolean数组标记,效率比set高一点

61813_accb913de2-image-20210323195515549.png

import java.util.*;

public class Main{
    static int N = 11, M = 360,P = 1 << 10,INF = 0x3f3f3f3f;
    static int n,m,p,k,s,idx;
    static int[][] g = new int[N * N][N * N];
    static int[] key = new int[P];
    static int[] h = new int[N * N],e = new int[M],ne = new int[M],w = new int[M];
    static int[][] dist = new int[N * N][P];
    static boolean[][] st = new boolean[N * N][P];
    static boolean[][] ss = new boolean[N * N][N * N];//相当于set,判断是不是已经连接过边了

    //链表模板
    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 void build(){
        int[] dx = {-1,0,1,0},dy = {0,1,0,-1};

        for (int i = 1 ; i <= n ; i ++ )
            for (int j = 1 ; j <= m ; j ++ )
                for (int u = 0 ; u < 4 ; u ++ ){
                    int x = i + dx[u];int y = j + dy[u];
                    if (x < 1 || x > n || y < 1 || y > m) continue;
                    int a = g[i][j],b = g[x][y];
                    //如果这个边没有标记过,说明还没有连接,那就连接一条有向边
                    if (!ss[a][b]) add(a,b,0);
                }
    }

    public static int bfs(){
        //首先将所有状态初始化成INF
        for (int i = 0 ; i < N * N; i ++ ) Arrays.fill(dist[i],INF);
        dist[1][0] = 0;//起点的位置距离是0,坐标(1,1)所映射的编号1,然后状态是0,当前还没有钥匙,
        //双端队列存的是一个PII(当前坐标映射的编号 ,状态即钥匙的二进制状态)
        Deque<PII>  q = new LinkedList<>();
        q.offer(new PII(1,0)); //

        while (q.size() != 0){
            PII t = q.poll();

            //这是跟dijkstra一样的,每次出队都标记
            if (st[t.x][t.y]) continue;
            st[t.x][t.y] = true;
            //如果已经走到了终点,直接返回终点的距离
            if (t.x == n * m) return dist[t.x][t.y];
            //第一步,如果这个点的位置有钥匙,那么需要将他们捡起来
            if (key[t.x] != 0){
                int state = t.y | key[t.x]; //用|这个符号将两个数的对应二进制位是1的加起来
                //然后更新,边权是0,因为没有改变位置,拿钥匙的时间是0
                if (dist[t.x][state] > dist[t.x][t.y]){
                    dist[t.x][state] = dist[t.x][t.y] ;
                    q.offerFirst(new PII(t.x,state)); //因为边权是0,所以加到队头
                }
            }

            //第二步,更新这个点的所有出边
            for (int i = h[t.x] ; i != -1 ; i = ne[i]){
                int j = e[i];
                //如果这个点有门,即w[i] != 0
                //然后当前这个点的钥匙二进制 与 对应的当前这个类型的门进行&,
                //如果是0,表示没有对应钥匙,直接continue,走不过去
                if (w[i] != 0 && ((t.y >> w[i] - 1 & 1) == 0)) continue;
                //反之则是有钥匙,那么可以走过去,更新
                if (dist[j][t.y] > dist[t.x][t.y] + 1){
                    dist[j][t.y] = dist[t.x][t.y] + 1;
                    //因为走过去需要时间是1,所以加到队尾
                    q.offerLast(new PII(j,t.y)); 
                }
            }
        }
        return -1;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        Arrays.fill(h,-1);

        n = scan.nextInt();
        m = scan.nextInt();
        p = scan.nextInt();
        k = scan.nextInt();

        for (int i = 1,t = 1; i <= n ; i ++ )
            for (int j = 1 ; j <= m ; j ++ )
                g[i][j] = t ++;

        while (k -- > 0){
            int x1 = scan.nextInt();
            int y1 = scan.nextInt();
            int x2 = scan.nextInt();
            int y2 = scan.nextInt();
            int c = scan.nextInt(); //c表示的钥匙的型号
            int a = g[x1][y1];
            int b = g[x2][y2];
            ss[a][b] = true; //标记已经连接过边了
            ss[b][a] = true; //标记已经连接过边了
            //如果不等于0,那就连接一条双向边,边权是门的型号
            if (c != 0) {
                add(a,b,c);
                add(b,a,c);
            }
        }

        build(); //这里是其他没有限制的边连双向边,边权是0,表示没有门

        //s表示钥匙的位置
        s = scan.nextInt();
        while (s -- > 0){
            int x = scan.nextInt();
            int y = scan.nextInt();
            int c = scan.nextInt();
            //将当前的点所映射的编号所对应的钥匙对应二进制位制成1
            key[g[x][y]] |= 1 << c - 1;
        }
        //最后输出bfs
        System.out.println(bfs());
    }
}
class PII{
    int x,y;
    public PII(int x,int y){
        this.x = x;
        this.y = y;
    }
}


活动打卡代码 AcWing 1131. 拯救大兵瑞恩

y总用Set存所有输入的边,这里用的是boolean数组标记,效率比set高一点

import java.util.*;
public class Main{
    static int N = 11, M = 360,P = 1 << 10,INF = 0x3f3f3f3f;
    static int n,m,p,k,s,idx;
    static int[][] g = new int[N * N][N * N];
    static int[] key = new int[P];
    static int[] h = new int[N * N],e = new int[M],ne = new int[M],w = new int[M];
    static int[][] dist = new int[N * N][P];
    static boolean[][] st = new boolean[N * N][P];
    static boolean[][] ss = new boolean[N * N][N * N];//相当于set,判断是不是已经连接过边了

    //链表模板
    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 void build(){
        int[] dx = {-1,0,1,0},dy = {0,1,0,-1};

        for (int i = 1 ; i <= n ; i ++ )
            for (int j = 1 ; j <= m ; j ++ )
                for (int u = 0 ; u < 4 ; u ++ ){
                    int x = i + dx[u];int y = j + dy[u];
                    if (x < 1 || x > n || y < 1 || y > m) continue;
                    int a = g[i][j],b = g[x][y];
                    //如果这个边没有标记过,说明还没有连接,那就连接一条有向边
                    if (!ss[a][b]) add(a,b,0);
                }
    }

    public static int bfs(){
        //首先将所有状态初始化成INF
        for (int i = 0 ; i < N * N; i ++ ) Arrays.fill(dist[i],INF);
        dist[1][0] = 0;//起点的位置距离是0,坐标(1,1)所映射的编号1,然后状态是0,当前还没有钥匙,
        //双端队列存的是一个PII(当前坐标映射的编号 ,状态即钥匙的二进制状态)
        Deque<PII>  q = new LinkedList<>();
        q.offer(new PII(1,0)); //

        while (q.size() != 0){
            PII t = q.poll();

            //这是跟dijkstra一样的,每次出队都标记
            if (st[t.x][t.y]) continue;
            st[t.x][t.y] = true;
            //如果已经走到了终点,直接返回终点的距离
            if (t.x == n * m) return dist[t.x][t.y];
            //第一步,如果这个点的位置有钥匙,那么需要将他们捡起来
            if (key[t.x] != 0){
                int state = t.y | key[t.x]; //用|这个符号将两个数的对应二进制位是1的加起来
                //然后更新,边权是0,因为没有改变位置,拿钥匙的时间是0
                if (dist[t.x][state] > dist[t.x][t.y]){
                    dist[t.x][state] = dist[t.x][t.y] ;
                    q.offerFirst(new PII(t.x,state)); //因为边权是0,所以加到队头
                }
            }

            //第二步,更新这个点的所有出边
            for (int i = h[t.x] ; i != -1 ; i = ne[i]){
                int j = e[i];
                //如果这个点有门,即w[i] != 0
                //然后当前这个点的钥匙二进制 与 对应的当前这个类型的门进行&,
                //如果是0,表示没有对应钥匙,直接continue,走不过去
                if (w[i] != 0 && ((t.y >> w[i] - 1 & 1) == 0)) continue;
                //反之则是有钥匙,那么可以走过去,更新
                if (dist[j][t.y] > dist[t.x][t.y] + 1){
                    dist[j][t.y] = dist[t.x][t.y] + 1;
                    //因为走过去需要时间是1,所以加到队尾
                    q.offerLast(new PII(j,t.y)); 
                }
            }
        }
        return -1;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        Arrays.fill(h,-1);

        n = scan.nextInt();
        m = scan.nextInt();
        p = scan.nextInt();
        k = scan.nextInt();

        for (int i = 1,t = 1; i <= n ; i ++ )
            for (int j = 1 ; j <= m ; j ++ )
                g[i][j] = t ++;

        while (k -- > 0){
            int x1 = scan.nextInt();
            int y1 = scan.nextInt();
            int x2 = scan.nextInt();
            int y2 = scan.nextInt();
            int c = scan.nextInt(); //c表示的钥匙的型号
            int a = g[x1][y1];
            int b = g[x2][y2];
            ss[a][b] = true; //标记已经连接过边了
            ss[b][a] = true; //标记已经连接过边了
            //如果不等于0,那就连接一条双向边,边权是门的型号
            if (c != 0) {
                add(a,b,c);
                add(b,a,c);
            }
        }

        build(); //这里是其他没有限制的边连双向边,边权是0,表示没有门

        //s表示钥匙的位置
        s = scan.nextInt();
        while (s -- > 0){
            int x = scan.nextInt();
            int y = scan.nextInt();
            int c = scan.nextInt();
            //将当前的点所映射的编号所对应的钥匙对应二进制位制成1
            key[g[x][y]] |= 1 << c - 1;
        }
        //最后输出bfs
        System.out.println(bfs());
    }
}
class PII{
    int x,y;
    public PII(int x,int y){
        this.x = x;
        this.y = y;
    }
}