边的删减

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

public class Main{
    static int N = 100010,M = 2*N;
    static int[] h = new int[N],e = new int[M],ne = new int[M],
    id = new int[M],w = new int[M];
    static long[] dis = new long[N];
    static boolean[] st = new boolean[N];
    static List<Integer> ans = new ArrayList<>();
    static int n,m,k,idx = 0,INF = 0x3f3f3f3f;
    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);
        for(int i = 1;i<=m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a,b,c,i);
            add(b,a,c,i);
        }

        dijkstra();
        Arrays.fill(st,false);
        dfs(1);
        System.out.println(ans.size());
        for(var ne:ans)
            System.out.print(ne+" ");
    }
    public static void dfs(int u){
        st[u] = true;
        for(int i = h[u];i!=-1;i = ne[i]){
            int j = e[i];
            if(dis[j] == dis[u]+w[i]&&!st[j]){
                if(ans.size()<k) ans.add(id[i]);
                dfs(j);
            }
        }
    }
    public static void dijkstra(){
        Arrays.fill(dis,Long.MAX_VALUE);
        PriorityQueue<long[]> pq 
            = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]>0?1:-1);
        dis[1] = 0;
        pq.add(new long[]{0,1});
        while(!pq.isEmpty()){
            long[] t = pq.poll();
            int ver = (int)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]){
                    dis[j] = dis[ver]+w[i];
                    pq.add(new long[]{dis[j],j});
                }
            }
        }
    }
    public static void add(int a,int b,int c,int d){
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        id[idx] = d;
        h[a] = idx++;
    }
}

交通规划

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

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

        dijkstra();

        int sum = 0;
        for(int u = 2;u<=n;u++){
            int cur = Integer.MAX_VALUE;
            for(int i = h[u];i!=-1;i = ne[i]){
                int j = e[i];
                if(dis[u] == dis[j]+w[i])
                    cur = Math.min(cur,w[i]);
            }
            sum+=cur;
        }
        System.out.println(sum);
    }
    public static void dijkstra(){
        Arrays.fill(dis,INF);
        PriorityQueue<int[]> pq 
            = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
        dis[1] = 0;
        pq.add(new int[]{0,1});
        while(!pq.isEmpty()){
            int[] t = pq.poll();
            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]){
                    dis[j] = dis[ver]+w[i];
                    pq.add(new int[]{dis[j],j});
                }
            }
        }
    }
    public static void add(int a,int b,int c){
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }
}