#pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; const int N=1e3+10; int n,m,t,x; int g[N][N],dist[N],st[N]; int startx,maxv=1e9; int p[N][N]; map<int,int>val,ans;//val存的是该点最大的价值,ans存路径 void Dijkstra(int x) { memset(dist,0x3f,sizeof dist); memset(st,0,sizeof st); dist[x]=0; for(int i=0;i<n;i++) { int t=-1; for(int j=1;j<=n;j++) if(!st[j]&&(t==-1 || dist[j]<dist[t] )) t=j; st[t]=1; for(int j=1;j<=n;j++) { if(dist[j]>dist[t]+g[t][j]) { dist[j]=dist[t]+g[t][j]; val[j]=val[t]+p[t][j]; ans[j]=t; } else if(dist[j]==dist[t]+g[t][j]) { if(val[j]<val[t]+p[t][j]) { val[j]=val[t]+p[t][j]; ans[j]=t; } } } } int temp=0; for(int i=1;i<=n;i++) temp=max(temp,dist[i]); if(temp<maxv) maxv=temp,startx=x; } int main(void) { memset(g,0x3f,sizeof g); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); g[a][b]=g[b][a]=c; p[a][b]=d,p[b][a]=d; } for(int i=1;i<=n;i++) Dijkstra(i);//每一个点跑一下最短路，找到最短路中最大的值，最小的值 printf("%d\n",startx); val.clear(),ans.clear(); Dijkstra(startx); scanf("%d",&t); while(t--) { int x; scanf("%d",&x); int node=x; vector<int>path; while(node) { path.push_back(node); node=ans[node]; } for(int i=path.size()-1;i>=0;i--) { if(i!=path.size()-1) printf("->"); printf("%d",path[i]); } printf("\n%d %d\n",dist[x],val[x]); } return 0; } 改成java代码

import java.util.*;

public class Main {
    static int N = 1010;
    static int[][] g = new int[N][N];
    static int[][] p = new int[N][N];
    static int[] dist = new int[N];
    static int[] st = new int[N];
    static Map<Integer, Integer> val = new HashMap<>();
    static Map<Integer, Integer> ans = new HashMap<>();

    public static void dijkstra(int x) {
        Arrays.fill(dist, 0x3f3f3f3f);
        Arrays.fill(st, 0);
        dist[x] = 0;
        for (int i = 0; i < N; i++) {
            int t = -1;
            for (int j = 1; j <= N; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            st[t] = 1;
            for (int j = 1; j <= N; j++) {
                if (dist[j] > dist[t] + g[t][j]) {
                    dist[j] = dist[t] + g[t][j];
                    val.put(j, val.get(t) + p[t][j]);
                    ans.put(j, t);
                } else if (dist[j] == dist[t] + g[t][j]) {
                    if (val.get(j) < val.get(t) + p[t][j]) {
                        val.put(j, val.get(t) + p[t][j]);
                        ans.put(j, t);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            int d = in.nextInt();
            g[a][b] = g[b][a] = c;
            p[a][b] = p[b][a] = d;
        }
        int maxv = Integer.MAX_VALUE, startx = 0;
        for (int i = 1; i <= n; i++) {
            dijkstra(i);
            int temp = 0;
            for (int j = 1; j <= n; j++) {
                temp = Math.max(temp, dist[j]);
            }
            if (temp < maxv) {
                maxv = temp;
                startx = i;
            }
        }
        System.out.println(startx);
        val.clear();
        ans.clear();
        dijkstra(startx);
        int t = in.nextInt();
        while (t-- > 0) {
            int x = in.nextInt();
            int node = x;
            List<Integer> path = new ArrayList<>();
            while (node != 0) {
                path.add(node);
                node = ans.get(node);
            }
            for (int i = path.size() - 1; i >= 0; i--) {
                if (i != path.size() - 1) {
                    System.out.print("->");
                }
                System.out.print(path.get(i));
            }
            System.out.println();
            System.out.println(dist[x] + " " + val.get(x));
        }
    }
}