如题= =自用模板

堆优化链式前向星迪杰斯特拉模板和链式前向星Spfa模板 注意迪杰斯特拉要预处理重边而Spfa不需要 最短路固定起点集的话可以另创一点和起点集中的点连一条距离为0的边从而转变成单源最短路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//堆优化迪杰斯特拉
import java.io.*;  
import java.util.*;  
public class Main {  
    static int[][]dis=new int[1005][1005];  
    public static void main(String[] args) {  
        FastScanner sc=new FastScanner();  
        PrintWriter pw=new PrintWriter(System.out);  
        Dij dij=new Dij();  
        while(sc.hasNext()){  
            int n=sc.nextInt();  
            int m=sc.nextInt();  
            int s=sc.nextInt();  
            dij.init();  
            for(int i=0;i<1005;i++){  
                for(int j=0;j<1005;j++){  
                    dis[i][j]=dij.INF;  
                }  
            }  
            for(int i=1;i<=m;i++){  
                int u=sc.nextInt();  
                int v=sc.nextInt();  
                int w=sc.nextInt();  
                dis[u][v]=Math.min(dis[u][v], w);  //预处理重边
            }  
            int w=sc.nextInt();  
            for(int i=0;i<w;i++){  
                int v=sc.nextInt();  
                dij.add_diredge(0, v, 0);  
            }  
            for(int i=1;i<1005;i++){  
                for(int j=1;j<1005;j++){  
                    if(dis[i][j]!=dij.INF){  
                        dij.add_diredge(i, j, dis[i][j]);  
                    }  
                }  
            }  
            dij.dijie(0);  
            if(dij.dis[s]==dij.INF){  
                pw.println(-1);  
            }else{  
                pw.println(dij.dis[s]);  
            }  
            pw.flush();  
        }  
  
    }  
  
}  
class Dij{  
    int maxn=1050;  
    int maxm=20050;  
    int cnt;  
    boolean[]p; //是否已经访问过 
    int[]dis;  //与起点的最短距离
    Edge[]edge;  //链式前向星边集
    int[]head;  
    int INF=0x3f3f3f3f;  
    int NINF=0xc0c0c0c0;  
    Dij(){  
        edge=new Edge[maxm];  
        for(int i=0;i<maxm;i++)edge[i]=new Edge();  
        head=new int[maxn];  
        p=new boolean[maxn];  
        dis=new int [maxn];  
    }  
    void init(){  
        Arrays.fill(p, false);  
        Arrays.fill(dis, 0);  
        Arrays.fill(head, -1);  
        cnt=0;  
    }    
    void add_diredge(int u ,int v,int w){  
        edge[cnt].to=v;  
        edge[cnt].w=w;  
        edge[cnt].next=head[u];  
        head[u]=cnt++;  
    }    
    void dijie(int s){    
        for(int i=0;i<maxn;i++)dis[i]=INF;    
        PriorityQueue<Node>o=new PriorityQueue<Node>();  
        dis[s]=0;    
        o.add(new Node(s,0));    
        while(!o.isEmpty()){    
            Node flag=o.poll();    
            int u=flag.hao;   
            if(p[u])continue;    
            int w=flag.w;    
            p[u]=true;    
            dis[u]=w;    
            for(int i=head[u];i!=-1;i=edge[i].next){    
                int t=edge[i].to;    
                if(dis[t]>dis[u]+edge[i].w)    
                dis[t]=dis[u]+edge[i].w;    
                o.add(new Node(t,dis[t]));    
            }    
        }    
    }    
}  
class Edge{  
    int next;  
    int to;  
    int w;  
}  
class Node implements Comparable<Node>{  
    int hao;  
    int w;  
    @Override  
    public int compareTo(Node a) {  
        if(this.w>a.w) return 1;  
        if(this.w<a.w) return -1;  
        return 0;  
    }  
    Node(int hao,int w){  
        this.hao=hao;  
        this.w=w;  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//Spfa
import java.io.*;  
import java.util.*;  
public class Main {  
  
    public static void main(String[] args) {  
        FastScanner sc=new FastScanner();  
        PrintWriter pw=new PrintWriter(System.out);  
        Spfa sp=new Spfa();  
        int t=sc.nextInt();  
        while(sc.hasNext()){  
            int n=sc.nextInt();  
            int m=sc.nextInt();  
            int w=sc.nextInt();  
            sp.init(n);  
            for(int o=1;o<=m;o++){  
                int u=sc.nextInt();  
                int v=sc.nextInt();  
                int cost=sc.nextInt();  
                sp.add_diredge(u, v, cost);  
                sp.add_diredge(v, u, cost);  
            }  
            for(int o=1;o<=w;o++){  
                int u=sc.nextInt();  
                int v=sc.nextInt();  
                int cost=sc.nextInt();  
                sp.add_diredge(u, v, -cost);  
            }  
            sp.spfa(1);  
            if(sp.hasnegativecircle)pw.println("YES");  
            else pw.println("NO");  
            pw.flush();  
        }  
  
    }  
  
}  
class Spfa{  
    int maxn=100500;  
    int maxm=200500;  
    int n;  
    Edge[]edge;  
    int[]head;  
    boolean[]inque;  
    int[]dis;  
    int cnt;  
    int[]js;  
    boolean hasnegativecircle;  
    //int[]path;  
    int INF=0x3f3f3f3f;  
    int NINF=0xc0c0c0c0;  
    Spfa(){  
        edge=new Edge[maxm];  
        for(int i=0;i<maxm;i++)edge[i]=new Edge();  
        head=new int[maxn];  
        inque=new boolean[maxn];  
        dis=new int[maxn];  
        js=new int[maxn];  
        //path=new int[maxn];  
    }  
    void init(int n){  
        Arrays.fill(inque, false);  
        Arrays.fill(dis, INF);  
        Arrays.fill(head, -1);  
        cnt=0;  
        Arrays.fill(js, 0);  
        this.n=n;  
        hasnegativecircle=false;  
    }  
    void spfa(int s){  
        Queue<Integer>queue=new LinkedList<Integer>();  
        for(int i=0;i<maxn;i++){  
            dis[i]=INF;  
            inque[i]=false;  
        }  
        dis[s]=0;  
        inque[s]=true;  
        js[s]++;  
        queue.add(s);  
        while(!queue.isEmpty()){  
            int u=queue.poll();  
            inque[u]=false;  
            for(int i=head[u];i!=-1;i=edge[i].next){  
                int v=edge[i].to;  
                int w=edge[i].w;  
                if(dis[u]+w<dis[v]){  
                    dis[v]=dis[u]+w;  
                    if(!inque[v]){  
                        queue.add(v);  
                        inque[v]=true;  
                        js[v]++;  
                        if(js[v]>=n){  
                            hasnegativecircle=true;  
                            return;  
                        }  
                    }  
                    //path[v]=u;  
                }  
            }  
        }  
    }  
    /*void printpath(int k){ 
        if(path[k]!=-1) printpath(path[k]); 
        System.out.print(k+" "); 
    }*/  
    void add_diredge(int u,int v,int w){  
        edge[cnt].to=v;  
        edge[cnt].w=w;  
        edge[cnt].next=head[u];  
        head[u]=cnt++;  
    }   
}  
class Edge{    
    int next;  
    int to;  
    int w;  
}