最直接的建图y总模板

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

题目:
热浪

堆优化版dijkstra

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

public class Main{
    static int N = 2510,M = 2*6210;
    static int[] h = new int[N],e = new int[M],
    ne = new int[M],w = new int[M];
    static boolean[] st = new boolean[N];
    static int[] dis = new int[N];
    static int idx = 0,n,m;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h,-1);
        n = sc.nextInt();
        m = sc.nextInt();
        int start = sc.nextInt();
        int end = sc.nextInt();
        for(int i = 0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a,b,c);
            add(b,a,c);
        }

        System.out.println(dijkstra(start,end));
    }
    public static int dijkstra(int start,int end){
        Arrays.fill(dis,0x3f3f3f3f);
        PriorityQueue<int[]> pq = new PriorityQueue<>
        ((o1,o2)->o1[0]-o2[0]);
        pq.add(new int[]{0,start});
        dis[start] = 0;
        while(!pq.isEmpty()){
            var t = pq.poll();
            int distance = t[0];
            int ver = t[1];
            if(ver == end) return dis[end];
            if(st[ver]) continue;
            for(int i = h[ver];i!=-1;i = ne[i]){
                int j = e[i];
                if(dis[j]>distance+w[i]){
                    dis[j] = distance+w[i];
                    pq.add(new int[]{dis[j],j});
                }
            }
            st[ver] = true;
        }
        return dis[end];
    }
    public static void add(int a,int b,int c){
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }
}

信使

spfa

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

public class Main{
    static int N = 110,M = 2*210;
    static int[] h = new int[N],e = new int[M],ne = new int[M],
    w = new int[M],dis = new int[M];
    static boolean[] st = new boolean[N];
    static int INF = 0x3f3f3f3f,idx = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h,-1);
        Arrays.fill(dis,INF);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a,b,c);
            add(b,a,c);
        }

        spfa();

        int max = 0;
        for(int i = 1;i<=n;i++)
            max = Math.max(dis[i],max);
        System.out.println(max);
    }
    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 spfa(){
        Queue<Integer> q = new LinkedList<>();
        dis[1] = 0;
        q.add(1);
        st[1] = true;
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            for(int i = h[t];i!=-1;i = ne[i]){
                int j = e[i];
                if(dis[j]>dis[t]+w[i]){
                    dis[j] = dis[t]+w[i];
                    if(!st[j]){
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }
    }
}

香甜的黄油

求最短路之和

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

public class Main{
    static int N = 810,M = 2*1460;
    static int[] h = new int[N],e = new int[M],
    ne = new int[M],w = new int[M],dis = new int[N],id = new int[N];
    static boolean[] st = new boolean[N];
    static int idx = 0,INF = 0x3f3f3f3f,n,q;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h,-1);
        q = sc.nextInt();
        n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 0;i<q;i++)
            id[i] = sc.nextInt();
        for(int i = 0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a,b,c);
            add(b,a,c);
        }
        int res = INF;
        for(int i = 1;i<=n;i++) res = Math.min(res,spfa(i));
        System.out.println(res);
    }
    public static int spfa(int u){
        Arrays.fill(st,false);
        Arrays.fill(dis,INF);
        Queue<Integer> qq = new LinkedList<>();
        qq.add(u);
        dis[u] = 0;
        st[u] = true;
        while(!qq.isEmpty()){
            int t = qq.poll();
            st[t] = false;
            for(int i = h[t];i!=-1;i = ne[i]){
                int j = e[i];
                if(dis[j]>dis[t]+w[i]){
                    dis[j] = dis[t]+w[i];
                    if(!st[j]){
                        st[j] = true;
                        qq.add(j);
                    }
                }
            }
        }
        int res = 0;
        for(int i = 0;i<q;i++){
            int j = id[i];
            if(dis[j]>=INF/2) return INF;
            res += dis[j];
        }
        return res;
    }
    public static void add(int a,int b,int c){
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }
}

最小花费

实际上是求最远路，即最大汇率，由于是乘算的所以更新的时候要用乘法

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

public class Main{
    static int N = 2010;
    static double[][] g = new double[N][N];
    static double[] dis = new double[N];
    static boolean[] st = new boolean[N];
    static int S,T,n,m;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            double z = (100-c)/100D;
            g[a][b] = g[b][a] = Math.max(g[a][b],z);
        }

        S = sc.nextInt();
        T = sc.nextInt();

        dijkstra();

        double ans = 100D/dis[T];

        System.out.printf("%.8f",ans);
    }

    public static void dijkstra(){
        Queue<Integer> q = new LinkedList<>();
        q.add(S);
        dis[S] = 1;
        for(int i = 1;i<=n;i++){

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

            st[t] = true;
            for(int j = 1;j<=n;j++)
                dis[j] = Math.max(dis[j],dis[t]*g[t][j]);
        }
    }
}

最优乘车

对于巴士线路内部的点，按照拓扑序来给这些点之间建边（前面的站能到后面，后面的不能到前面）
由于要计算的是最少换乘次数，可以转化成坐了多少趟车，如果两个点直接能直接到达，那么这两个点的距离一定是1
因为线路内的两个点一定存在一条权值为1的边，如果两个点不能直接到达，则需要换乘
由于第一趟车是不计入换乘的，所以最终的答案还需要=1

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

public class Main{
    static int N = 510;
    static boolean[][] g = new boolean[N][N];
    static int[] dis = new int[N];
    static int INF = 0x3f3f3f3f;
    static int n;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        n = sc.nextInt();
        sc.nextLine();
        for(int i = 0;i<m;i++){
            String[] s = sc.nextLine().split(" ");
            int sz = s.length;
            for(int j = 0;j<sz;j++)
                for(int k = j+1;k<sz;k++){
                    int a = Integer.parseInt(s[j]);
                    int b = Integer.parseInt(s[k]);
                    g[a][b] = true;
                }
        }

        bfs();

        if(dis[n] >= INF/2)System.out.println("NO");
        else{
            dis[n] = Math.max(dis[n]-1,0);
            System.out.println(dis[n]);
        }
    }
    public static void bfs(){
        Arrays.fill(dis,INF);
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        dis[1] = 0;
        while(!q.isEmpty()){
            int t = q.poll();
            if(t == n) break;

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

昂贵的聘礼

建立一个虚拟原点，连接每一样物品，再依据物品的依赖关系建图
最后再枚举等级，因为最多只有100组

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

public class Main{
    static int N = 110;
    static int[] dis = new int[N],le = new int[N];
    static boolean[] st = new boolean[N];
    static int[][] g = new int[N][N];
    static int INF = 0x3f3f3f3f,Z,m,n;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        Z = n+1;
        sc.nextLine();
        for(int i = 0;i<N;i++)
            Arrays.fill(g[i],INF);
        for(int i = 0;i<N;i++)
            g[i][i] = 0;
        for(int i = 1;i<=n;i++){
            String[] s = sc.nextLine().split(" ");
            g[Z][i] = Integer.parseInt(s[0]);
            le[i] = Integer.parseInt(s[1]);
            int size = Integer.parseInt(s[2]);
            for(int j = 0;j<size;j++){
                s = sc.nextLine().split(" ");
                int ver = Integer.parseInt(s[0]);
                g[ver][i] = Integer.parseInt(s[1]);
            }
        }
        int minPrice = g[Z][1];
        for(int i = 1;i+m<=100;i++){
            dijkstra(i,i+m);
            minPrice = Math.min(minPrice,dis[1]);
        }

        System.out.println(minPrice);
    }
    public static void dijkstra(int startL,int startR){
        Arrays.fill(st,false);
        Arrays.fill(dis,INF);
        dis[Z] = 0;
        for(int i = 1;i<=n+1;i++){

            int t = -1;
            for(int j = 1;j<=n+1;j++)
                if(!st[j]&&(t == -1||dis[j]<dis[t]))
                    t = j;
            st[t] = true;
            for(int j = 1;j<=n+1;j++)
                if(le[j]>=startL&&le[j]<=startR)
                    dis[j] = Math.min(dis[j],dis[t]+g[t][j]);
        }
    }
}

道路与航线

由于这题卡spfa，所以不得不另辟蹊径
由于道路是双向的，航线是单向的，对于每一个以双向道路连接的集合，我们可以把它视作一个点
这些点直接都是以单向边连接的，所以更新最短路时都是依据拓扑序更新的，对于点内部的点
可以直接使用最短路算法

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

public class Main{
    static int N = 25010,M = 3*50010;
    static int[] h = new int[N],e = new int[M],ne = new int[M],
    w = new int[M],dist = new int[M],id = new int[N],in = new int[N];
    static List<Integer>[] block = new List[N];
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] st = new boolean[N];
    static int idx = 0,n,rm,pm,s,INF = 0x3f3f3f3f,dcnt = 0;
    public static void main(String[] args)throws IOException{
        BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
        Arrays.fill(h,-1);
        String[] data = br.readLine().split(" ");
        n = Integer.parseInt(data[0]);
        rm = Integer.parseInt(data[1]);
        pm = Integer.parseInt(data[2]);
        s = Integer.parseInt(data[3]);
        for(int i = 0;i<rm;i++){
            data = br.readLine().split(" ");
            int a = Integer.parseInt(data[0]);
            int b = Integer.parseInt(data[1]);
            int c = Integer.parseInt(data[2]);
            add(a,b,c);
            add(b,a,c);
        }

        for(int i = 1;i<=n;i++)
            if(!st[i]){
                block[++dcnt] = new LinkedList<>();
                dfs(i,dcnt);
            } 

        for(int i = 0;i<pm;i++){
            data = br.readLine().split(" ");
            int a = Integer.parseInt(data[0]);
            int b = Integer.parseInt(data[1]);
            int c = Integer.parseInt(data[2]);
            add(a,b,c);
            in[id[b]]++;
        }

        topoSort();

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

    public static void topoSort(){
        Arrays.fill(dist,INF);
        Arrays.fill(st,false);
        dist[s] = 0;
        for(int i = 1;i<=dcnt;i++)
            if(in[i] == 0) q.add(i);

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

    public static void dijkstra(int bid){
        PriorityQueue<int[]> pq 
            = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
        for(var ne:block[bid]) pq.add(new int[]{dist[ne],ne});
        while(!pq.isEmpty()){
            var t = pq.poll();
            int distance = t[0];
            int ver = 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];
                    if(id[j] == id[ver]) {
                        pq.add(new int[]{dist[j],j});
                    }
                }
                if(id[j] != id[ver] && --in[id[j]] == 0)
                    q.add(id[j]);
            }
        }
    }

    public static void dfs(int u,int bid){
        st[u] = true;
        id[u] = bid;
        block[bid].add(u);
        for(int i = h[u];i!=-1;i = ne[i]){
            int j = e[i];
            if(!st[j]) dfs(j,bid);
        }
    }
    public static void add(int a,int b,int c){
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }
}

紧急情况

先用dijkstra算法计算最短路和最短路数目（因为dijkstra满足拓扑序）
再记录每一个点是由哪些点转移过来的，然后用bfs反向建边
最后再跑一遍最短路算法（dijkstra系列或者bellman_ford系列）

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

public class Main{
    static int N = 510,M = 2410;
    static int[] h = new int[N],uh = new int[N],e = new int[M],
    ne = new int[M],w = new int[M],dis = new int[N],
    val = new int[N],cnt = new int[N];
    static boolean[] st = new boolean[N];
    static List<Integer>[] pre = new List[N];
    static int idx = 0,n,m,start,end,INF = 0x3f3f3f3f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h,-1);
        Arrays.fill(uh,-1);
        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();
        end = sc.nextInt();
        for(int i = 0;i<n;i++)
            val[i] = sc.nextInt();
        for(int i = 0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(h,a,b,c);
            add(h,b,a,c);
        }

        dijkstra();

        System.out.print(cnt[end]+" "+dis[start]);

    }
    public static void dijkstra(){
        Arrays.fill(dis,INF);
        dis[start] = 0;
        cnt[start] = 1;
        PriorityQueue<int[]> pq 
            = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
        pq.add(new int[]{0,start});
        while(!pq.isEmpty()){
            int[] t = pq.poll();
            int distance = t[0];
            int ver = t[1];
            if(st[ver]) continue;
            st[ver] = true;

            for(int i = h[ver];i!=-1;i = ne[i]){
                int j = e[i];
                if(dis[j]>dis[ver]+w[i]){
                    pre[j] = new ArrayList<>();
                    pre[j].add(ver);
                    dis[j] = dis[ver]+w[i];
                    cnt[j] = cnt[ver];
                    pq.add(new int[]{dis[j],j});
                }else if(dis[j] == dis[ver]+w[i]){
                    cnt[j] += cnt[ver];
                    pre[j].add(ver);
                }
            }
        }

        //bfs
        Queue<Integer> q = new LinkedList<>();
        q.add(end);
        while(!q.isEmpty()){
            int t = q.poll();
            if(pre[t]!=null){
                for(var ne:pre[t]){
                    q.add(ne);
                    add(uh,t,ne,0);
                }
            }
        }

        Arrays.fill(dis,-INF);
        Arrays.fill(st,false);
        dis[end] = val[end];
        q.add(end);
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            //System.out.println(t);
            for(int i = uh[t];i != -1; i = ne[i]){
                int j = e[i];
                if(dis[j]<dis[t]+val[j]){
                    dis[j] = dis[t]+val[j];
                    if(!st[j]){
                        st[j] = true;
                        q.add(j);
                    }
                }
            }
        }
    }
    public static void add(int[] h,int a,int b,int c){
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }
}

与上一题类似的还有
旅行计划

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

public class Main{
    static int N = 2500,M = 2500;
    static int[] h = new int[N],uh = new int[N],
    e = new int[M],ne = new int[M],w1 = new int[N],
    w2 = new int[N],dis = new int[N],path = new int[N];
    static boolean[] st = new boolean[N];
    static List<int[]>[] pre = new List[N];
    static int n,m,idx = 0,S,D,INF = 0x3f3f3f3f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Arrays.fill(path,-1);
        Arrays.fill(h,-1);
        Arrays.fill(uh,-1);
        n = sc.nextInt();
        m = sc.nextInt();
        S = sc.nextInt();
        D = sc.nextInt();
        for(int i = 0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int d = sc.nextInt();
            add(h,a,b,c,d);
            add(h,b,a,c,d);
        }

        dijkstra(S,h,w1,w2,0);
        int ans1 = dis[D];
        dijkstra(D,uh,w1,w2,1);
        int ans2 = dis[S];
        int end = S;
        while(true){
            System.out.print(end+" ");
            if(end == D) break;
            end = path[end];
        }
        System.out.print(ans1+" "+ans2);
    }
    public static void dijkstra(int start,int[] h,int[] w,int[] extra,int f){
        Arrays.fill(dis,INF);
        Arrays.fill(st,false);
        dis[start] = 0;
        PriorityQueue<int[]> pq 
            = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
        pq.add(new int[]{0,start});
        while(!pq.isEmpty()){
            int[] t = pq.poll();
            int ver = t[1];
            if(st[ver]) continue;
            st[ver] = true;
            // if(f == 1)System.out.println(ver);
            for(int i = h[ver];i!=-1;i = ne[i]){
                int j = e[i];
                // if(f == 1)
                //     System.out.println(ver+" "+j+" "+w[i]);
                if(dis[j]>dis[ver]+w[i]){
                    dis[j] = dis[ver]+w[i];
                    if(f == 0){
                        pre[j] = new ArrayList<>();
                        pre[j].add(new int[]{ver,extra[i]});
                    }
                    if(f == 1) path[j] = ver;
                    pq.add(new int[]{dis[j],j});
                }else if(dis[j] == dis[ver]+w[i])
                    pre[j].add(new int[]{ver,extra[i]});
            }
        }

        if(f == 1) return;

        Arrays.fill(st,false);
        Queue<Integer> q = new LinkedList<>();
        q.add(D);
        while(!q.isEmpty()){
            int t = q.poll();
            if(pre[t]!=null){
                for(var ne:pre[t]){
                    int ver = ne[0];
                    int distance = ne[1];
                    add(uh,t,ver,distance,0);
                    q.add(ver);
                }
            }
        }
    }
    public static void add(int[] h,int a,int b,int c,int d){
        e[idx] = b;
        ne[idx] = h[a];
        w1[idx] = c;
        w2[idx] = d;
        h[a] = idx++;
    }
}

汽车加油行驶

每个状态要用三个值来表示，坐标（x，y） 步数：k
把状态映射成一维，看作一个点
当有加油站时，必须加油，然后向四个反向扩展
当没有加油站时，可以选择建立加油站，然后向四个方向扩展

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

public class Main{
    static int N = 110,K = 12,M = 500010,Q = N*N*K;
    static int[] h = new int[Q],e = new int[M],ne = new int[M],
    w = new int[M],dis = new int[Q];
    static boolean[] st = new boolean[Q];
    static int[][] g = new int[N][N];
    static int[][][] map = new int[N][N][K];
    static int n,k,idx = 0,A,B,C,INF = 0x3f3f3f3f,c;
    public static void main(String[] args){
        init();
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h,-1);
        n = sc.nextInt();
        k = sc.nextInt();
        A = sc.nextInt();
        B = sc.nextInt();
        C = sc.nextInt();
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)
                g[i][j] = sc.nextInt();

        build();

        dijkstra();

        int ans = INF;
        for(int i = 0;i<=k;i++)
            ans = Math.min(ans,dis[map[n][n][i]]);
        System.out.println(ans);

    }
    public static void dijkstra(){
        Arrays.fill(dis,INF);
        dis[map[1][1][k]] = 0;
        PriorityQueue<int[]> pq 
            = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
        pq.add(new int[]{0,map[1][1][k]});
        while(!pq.isEmpty()){
            int[] t = pq.poll();
            int ver = t[1],distance = t[0];
            //System.out.println(ver);
            if(st[ver]) continue;
            st[ver] = true;
            for(int i = h[ver];i!=-1; i = ne[i]){
                int j = e[i];
                //System.out.println(j);
                if(dis[j]>dis[ver]+w[i]){
                    dis[j] = dis[ver]+w[i];
                    pq.add(new int[]{dis[j],j});
                }
            }
        }
    }
    public static void build(){
        for(int i = 1;i<=n;i++) 
            for(int j = 1;j<=n;j++){
                if(g[i][j] == 1){
                    for(int u = 0;u<k;u++)
                        add(map[i][j][u],map[i][j][k],A);
                    if(i>1) add(map[i][j][k],map[i-1][j][k-1],B);
                    if(i<n) add(map[i][j][k],map[i+1][j][k-1],0);
                    if(j>1) add(map[i][j][k],map[i][j-1][k-1],B);
                    if(j<n) add(map[i][j][k],map[i][j+1][k-1],0);
                }else{
                    for(int u = 0;u<k;u++)
                        add(map[i][j][u],map[i][j][k],A+C);
                    for(int u = 1;u<=k;u++){
                        if(i>1) add(map[i][j][u],map[i-1][j][u-1],B);
                        if(i<n) add(map[i][j][u],map[i+1][j][u-1],0);
                        if(j>1) add(map[i][j][u],map[i][j-1][u-1],B);
                        if(j<n) add(map[i][j][u],map[i][j+1][u-1],0);
                    }
                }
            }
    }
    public static void add(int a,int b,int c){
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }
    public static void init(){
        for(int i = 1,t = 1;i<N;i++)
            for(int j = 1;j<N;j++)
                for(int k = 0;k<K;k++)
                    map[i][j][k] = t++;
    }
}