头像

rfx




离线:15小时前


最近来访(109)
用户头像
acwhr
用户头像
pixrij
用户头像
IdealDragon
用户头像
Undermoon1412
用户头像
01_92
用户头像
NoWordsLand
用户头像
厉飞雨
用户头像
zyz529
用户头像
Spade_NL
用户头像
江南牧牛人
用户头像
那必须得是我了
用户头像
hackstd
用户头像
noobs
用户头像
做事要有遗逝感
用户头像
fangqing
用户头像
mhmh
用户头像
zhouyuhao
用户头像
人生如戏ba
用户头像
小小_88
用户头像
.isEmpty

活动打卡代码 AcWing 341. 最优贸易

rfx
15小时前
import java.util.*;
import java.io.*;

public class Main {
    static final int N = 100010;
    static final int M = 2000010;
    static int[] hs = new int[N];
    static int[] ht = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int[] q = new int[N];
    static int[] dmin = new int[N];
    static int[] dmax = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m, idx;

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

    static void spfa (int[] h, int[] dist, int type) {
        int hh = 0, tt = 1;

        if (type == 0) {
            Arrays.fill(dist, 0x3f3f3f3f);
            dist[1] = w[1];
            q[0] = 1;
        } else {
            Arrays.fill(dist, -0x3f3f3f3f);
            dist[n] = w[n];
            q[0] = n;
        }

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

            for (int i = h[t]; i !=-1; i = ne[i]) {
                int j = e[i];
                if (type == 0 && dist[j] > Math.min(dist[t], w[j]) || type == 1 && dist[j] < Math.max(dist[t], w[j])) {
                    if (type == 0) 
                        dist[j] = Math.min(dist[t], w[j]);
                    else dist[j] = Math.max(dist[t], w[j]);

                    if (!st[j]) {
                        q[tt ++] = j;
                        if (tt == N) tt = 0;
                        st[j] = true;
                    }
                }
            }
        }
    }

    public static void main (String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String line = reader.readLine();
        String[] tmp = line.split(" ");
        n = Integer.parseInt(tmp[0]);
        m = Integer.parseInt(tmp[1]);
        line = reader.readLine();
        tmp = line.split(" ");
        for (int i = 1; i <= n; i ++ ){
            w[i] = Integer.parseInt(tmp[i - 1]);
        } 
        Arrays.fill(hs, -1);
        Arrays.fill(ht, -1);
        while (m -- > 0) {
            line = reader.readLine();
            tmp = line.split(" ");
            int a = Integer.parseInt(tmp[0]);
            int b = Integer.parseInt(tmp[1]);
            int type = Integer.parseInt(tmp[2]);
            add(a, b, hs);
            add(b, a, ht);
            if (type == 2) {
                add(b, a, hs);
                add(a, b, ht);
            }
        }

        spfa(hs, dmin, 0);
        spfa(ht, dmax, 1);

        int res = 0;

        for (int i = 1; i <= n; i ++ )
            res = Math.max(res, dmax[i] - dmin[i]);

        System.out.println(res);

    }
}



活动打卡代码 AcWing 342. 道路与航线

rfx
1天前
import java.util.*;

public class Main {
    static final int N = 25010;
    static final int M = 50000 * 3 + 10;
    static int[] id = new int[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int[] dist = new int[N];
    static int[] din = new int[N];
    static List<Integer>[] block = new List[N];
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] st = new boolean[N];
    static int bcnt;
    static int idx;
    static int n, mr, mp, S;

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

    static void dfs (int u, int bid) {
        id[u] = bid;
        block[bid].add(u);
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (id[j] == 0)
                dfs(j, bid);
        }
    }

    static void topsort () {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[S] = 0;

        for (int i = 1; i <= bcnt; i ++ ) 
            if (din[i] == 0)
                q.offer(i);

        while (!q.isEmpty()) {
            int t = q.poll();
            dijkstra(t);
        }
    }

    static void dijkstra (int bid) {
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        for (int u : block[bid])
            heap.offer(new int[]{dist[u], u});

        while (!heap.isEmpty()) {
            int[] t = heap.poll();

            int ver = t[1], distance = t[0];
            if (st[ver]) continue;
            st[ver] = true;

            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (id[j] != id[ver] && -- din[id[j]] == 0) q.offer(id[j]);
                if (dist[j] > dist[ver] + w[i]) {
                    dist[j] = dist[ver] + w[i];
                    if (id[j] == id[ver]) heap.offer(new int[]{dist[j], j});
                }
            }
        }
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        mr = sc.nextInt();
        mp = sc.nextInt();
        S = sc.nextInt();
        for (int i = 0; i <= n; i ++)
            block[i] = new ArrayList<>();

        Arrays.fill(h, -1);
        while (mr -- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a, b, c);
            add(b, a, c);
        }

        for (int i = 1; i <= n; i ++ ) 
            if (id[i] == 0)
                dfs(i, ++bcnt);

        while (mp -- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            din[id[b]] ++;
            add(a, b, c);
        }

        topsort();

        for (int i = 1; i <= n; i ++ )
            if (dist[i] > 0x3f3f3f3f / 2) System.out.println("NO PATH");
            else System.out.println(dist[i]);
    }
}


活动打卡代码 AcWing 340. 通信线路

rfx
2天前
import java.util.*;

public class Main {
    static final int N = 1010;
    static final int M = 20010;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static Deque<Integer> q = new LinkedList<>();
    static int n, m, k, idx;

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

    static boolean check (int s) {
        Arrays.fill(dist, 0x3f3f3f3f);
        Arrays.fill(st, false);
        dist[1] = 0;
        q.offer(1);
        while (!q.isEmpty()) {
            int t = q.poll();
            if (st[t]) continue;
            st[t] = true;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                int v = w[i] > s ? 1 : 0;
                if (dist[t] + v < dist[j]) {
                    dist[j] = dist[t] + v;
                    if (v == 0) q.offerFirst(j);
                    else q.offerLast(j);
                }
            }
        }
        return dist[n] <= k;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        Arrays.fill(h, -1);
        while (m -- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a, b, c);
            add(b, a, c);
        }
        int l = 0, r = 1000001;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        if (r == 1000001) r = -1;
        System.out.println(r);
    }
}


活动打卡代码 AcWing 1135. 新年好

rfx
4天前
import java.util.*;

public class Main {
    static final int N = 50010, M = 200010;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] w = new int[M];
    static int[] ne = new int[M];
    static int[][] dist = new int[6][N];
    static int[] source = new int[6];
    static boolean[] st = new boolean[N];
    static int n, m, idx;

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

    static void dijkstra (int start, int[] dist) {
        Arrays.fill(dist, 0x3f3f3f3f);
        Arrays.fill(st, false);
        dist[start] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(n, Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{start, 0});
        while (!pq.isEmpty()) {
            int[] t = pq.poll();
            int ver = t[0];
            int distance = t[1];
            if (st[ver]) continue;
            st[ver] = true;
            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > distance + w[i]) {
                    dist[j] = distance + w[i];
                    pq.offer(new int[] {j, dist[j]});
                }
            }
        }
    }

    static int dfs (int u, int start, int distance) {
        if (u == 6) return distance;

        int res = 0x3f3f3f3f;
        for (int i = 1; i <= 5; i ++ ) {
            if (!st[i]) {
                int next = source[i];
                st[i] = true;
                res = Math.min(res, dfs(u + 1, i, distance + dist[start][next]));
                st[i] = false;
            }
        }

        return res;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner (System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        source[0] = 1;
        for (int i = 1; i <= 5; i ++ ) source[i] = sc.nextInt();

        Arrays.fill(h, -1);
        while (m -- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a, b, c);
            add(b, a, c);
        }
        for (int i = 0; i < 6; i ++ ) dijkstra(source[i], dist[i]);

        Arrays.fill(st, false);
        System.out.println(dfs(1, 0, 0));
    }
}



rfx
4天前

单源最短路模型st数组存储的含

  • 朴素dijkstra和堆优化dijkstra使用的是用来存储已经确认最短路的点
  • spfa是用来存储队列中的点


活动打卡代码 AcWing 920. 最优乘车

rfx
5天前
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static final int N = 510;
    static boolean[][] g = new boolean[N][N];
    static int[] dist = new int[N];
    static int[] q = new int[N];
    static int[] stop = new int[N];
    static int n, m;

    static void bfs () {
        int hh = 0, tt = 0;
        Arrays.fill(dist, 0x3f3f3f3f);
        q[0] = 1;
        dist[1] = 0;

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

            for (int i = 1; i <= n; i ++ )
                if (g[t][i] && dist[i] > dist[t] + 1) {
                    dist[i] = dist[t] + 1;
                    q[++ tt] = i;
                }
        }
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        sc.nextLine();
        while (m -- > 0) {
            String line = sc.nextLine();
            String[] sts = line.split(" ");
            for (int i = 0; i < sts.length; i ++ )
                stop[i] = Integer.parseInt(sts[i]);
            for (int i = 0; i < sts.length; i ++ )
                for (int j = i + 1; j < sts.length; j ++ )
                    g[stop[i]][stop[j]] = true;
        }

        bfs();

        if (dist[n] == 0x3f3f3f3f) System.out.println("NO");
        else System.out.println(Math.max(0, dist[n] - 1));
    }
}


活动打卡代码 AcWing 903. 昂贵的聘礼

rfx
5天前
import java.util.*;

public class Main {
    static final int N = 110;
    static int[] dist = new int[N];
    static int[] level = new int[N];
    static boolean[] st = new boolean[N];
    static int[][] w = new int[N][N];
    static int n, m;

    static int dijkstra (int down, int up) {
        Arrays.fill(dist, 0x3f3f3f3f);
        Arrays.fill(st, false);

        dist[0] = 0;
        for (int i = 1; i <= n + 1; i ++ ) {
            int t = -1;
            for (int j = 0; j <= n; j ++ ) 
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;

            st[t] = true;
            for (int j = 1; j <= n; j ++ )
                if (level[j] >= down && level[j] <= up)
                    dist[j] = Math.min(dist[j], dist[t] + w[t][j]);
        }

        return dist[1];
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        for (int[] ints : w)
            Arrays.fill(ints, 0x3f3f3f3f);

        for (int i = 1; i <= n; i ++ ) w[i][i] = 0;

        for (int i = 1; i <= n; i ++ ) {
            int price = sc.nextInt();
            level[i] = sc.nextInt();
            int cnt = sc.nextInt();
            w[0][i] = Math.min(price, w[0][i]);
            while (cnt -- > 0) {
                int id = sc.nextInt();
                int cost = sc.nextInt();
                w[id][i] = Math.min(w[id][i], cost);
            }
        }

        int res = 0x3f3f3f3f;
        for (int i = level[1] - m; i <= level[1]; i ++ ) {
            res = Math.min(res, dijkstra(i, i + m));
        }

        System.out.println(res);
    }
}


活动打卡代码 AcWing 823. 排列

rfx
6天前
let buf = "";
let st = []
let ans = []
let res = []

process.stdin.on("readable", function() {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});

let dfs = (u, n) => {
    if (u == n) {
        res.push(ans.join(' '))
        return;
    }
    for (let i = 1; i <= n; i ++ ) {
        if (st[i]) continue;
        st[i] = true;
        ans[u] = i;
        dfs(u + 1, n)
        st[i] = false
    }
}

process.stdin.on("end", function() {
    let n = parseInt(buf.split('\n')[0])
    dfs(0, n)
    for (let re of res) {
        console.log(re)
    }
});


活动打卡代码 AcWing 818. 数组排序

rfx
6天前
let buf = "";
let tmp = []

process.stdin.on("readable", function() {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});


let merge_sort = (q, l, r) => {
    if (l >= r) return;
    let mid = l + r >> 1;
    merge_sort(q, l, mid)
    merge_sort(q, mid + 1, r);
    let i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k ++] = q[i ++]
        else tmp[k ++] = q[j ++]
    }
    while (i <= mid ) tmp[k ++ ] = q[i ++]
    while (j <= r) tmp[k ++ ] = q[j ++]
    for (i = l, j = 0; i <= r; i ++, j ++)
     q[i] = tmp[j]
}

process.stdin.on("end", function() {
    let lines = buf.split('\n')
    let [n, a, b] = lines[0].split(' ').map(x => {return parseInt(x)})
    let num = lines[1].split(' ').map(x => {return parseInt(x)})
    merge_sort(num, a, b)
    console.log(num.join(' '))
});


活动打卡代码 AcWing 808. 最大公约数

rfx
6天前
let buf = "";

process.stdin.on("readable", function() {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});

let gcd = (a, b) => {
    return b ? gcd(b, a % b) : a;
}

process.stdin.on("end", function() {
    let [a, b] = buf.split(' ').map(x => {return parseInt(x)})
    console.log(gcd(a, b))
});