仓库配送

懒得写dijskra了。。就Floyd应付一下

int dijskra(vector<vector<int>>& graph, int N, int source)
{
    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
    int ans = INT_MIN;
    for (int i = 1; i <= N; ++i) {
        ans = max(ans, graph[source][i]);
    }
    if (ans == INT_MAX)return -1;
    return ans;
}
int main()
{
    int N, K, M, v, u, w;
    cin >> N >> K >> M;
    vector<vector<int>> graph(N + 1, vector<int>(N + 1, INT_MAX));
    for (int i = 0; i < M; ++i) {
        cin >> v >> u >> w;
        graph[v][u] = w;
    }
    for (int i = 0; i < N; ++i) {
        graph[i][i] = 0;
    }
    cout << dijskra(graph, N, K);
    return 0;
}

套一下dijkstra模板就好了

import java.util.*;
public class Main {

    static int max = Integer.MAX_VALUE / 2;

    static int N;
    static int k;
    static List> adj;
    static int[] dist;
    static boolean[] st;
    static PriorityQueue heap = new PriorityQueue();

    static class Node implements Comparable {
        int idx;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }

    static void dijkstra() {
        Arrays.fill(dist, max);
        dist[k] = 0;

        heap.offer(k);
        while (!heap.isEmpty()) {
            int idx = heap.poll();
            st[idx] = true;

            // 更新邻接的节点
            for (Node v : adj.get(idx)) {
                if (dist[v.idx] > dist[idx] + v.cost) {
                    dist[v.idx] = dist[idx] + v.cost;
                    heap.offer(v.idx);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        k = sc.nextInt();
        int m = sc.nextInt();
        adj = new ArrayList();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList());
        }
        dist = new int[N + 1];
        st = new boolean[N + 1];

        while (m-- > 0) {
            adj.get(sc.nextInt()).add(new Node(sc.nextInt(), sc.nextInt()));
        }

        dijkstra();

        // 判断是否都可达
        int time = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] >= max) {
                time = -1;
                break;
            } else {
                time = Math.max(time, dist[i]);
            }
        }

        System.out.println(time);
    }
}

import java.io.*;
import java.util.*;
public class Main{
    public static class Node{
        public int n;
        public int dis;
        public Node(int n, int dis){
            this.n   = n;
            this.dis = dis;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = " ";
        while((str = br.readLine()) != null){
            String[] str_array = str.split(" ");
            int n   = Integer.parseInt(str_array[0]);
            int ori = Integer.parseInt(str_array[1]);
            int m   = Integer.parseInt(str_array[2]);
            int[][] graph = new int[n+1][n+1];//== 0没有边 >0才有边
            for(int i = 0; i < m; ++i){
                str_array   = br.readLine().split(" ");
                int from    = Integer.parseInt(str_array[0]);
                int to      = Integer.parseInt(str_array[1]);
                int weights = Integer.parseInt(str_array[2]);
                graph[from][to] = weights;
            }
            int[] dis = new int[n+1];
            int[] vis = new int[n+1];
            dis[ori] = 0;
            for(int i = 1; i <= n; ++i){
                if(ori == i) continue;
                dis[i] = Integer.MAX_VALUE;
            }
            PriorityQueue<Node> heap = new PriorityQueue<>((o1,o2)->{return o1.dis - o2.dis;});
            for(int i = 1; i <= n; ++i) heap.offer(new Node(i,dis[i]));
            Node node;
            int num = 0;
            while(true){
                
                while(heap.size() != 0 && vis[heap.peek().n] == 1) heap.poll();
                node = heap.poll();
                vis[node.n] = 1;
                if(++num == n) break;
                for(int i = 1; i <= n; ++i){
                    if(graph[node.n][i] > 0 && vis[i] == 0){
                        if(dis[node.n] + graph[node.n][i] < dis[i]){
                            dis[i] = dis[node.n] + graph[node.n][i];
                            heap.offer(new Node(i,dis[i]));
                        }
                    }
                }
            }
            int max = -1;
            for(int i = 1; i <= n; ++i) max = Math.max(max,dis[i]);
            System.out.println(max == Integer.MAX_VALUE? -1 : max);
        }
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String[] info1= sc.nextLine().split(" ");
        int N=Integer.parseInt(info1[0]), K=Integer.parseInt(info1[1]), M=Integer.parseInt(info1[2]);
        HashMap<Integer, HashMap<Integer, Integer>> graph=new HashMap<>();
        for(int i=1; i<=M; i++) {
            String[] edge=sc.nextLine().split(" ");
            int from=Integer.parseInt(edge[0]), to=Integer.parseInt(edge[1]), time=Integer.parseInt(edge[2]);
            if(!graph.containsKey(from)) graph.put(from, new HashMap<>());
            graph.get(from).put(to, time);
        }
        boolean[] visited=new boolean[N+1];
        
        int count=N;
        Queue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[1]-b[1];
            }
        });
        queue.add(new int[]{K, 0});
        
        int res=0;
        while(!queue.isEmpty()) {
            int[] cur=queue.poll();
            if(!visited[cur[0]]) {
                res=Math.max(res, cur[1]);
                visited[cur[0]]=true;
                count--;
                if(graph.containsKey(cur[0])) {
                    HashMap<Integer, Integer> neigh_node=graph.get(cur[0]);
                    for(int neigh:neigh_node.keySet()) {
                        if(!visited[neigh]) {
                            queue.add(new int[]{neigh, cur[1]+neigh_node.get(neigh)});
                        }
                    }
                }
            }
        }
        
        if(count>0) System.out.print(-1);
        else System.out.print(res);

        sc.close();
    }
}

贴一个堆优化的dijskra
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int N = 40, M = 1e3, INF = 0x3f3f3f3f;
int n, st;

int h[N], ne[M], e[M], w[M], idx;

int dis[N];
bool use[N];

void add(int l, int r, int x)
{
    ne[idx] = h[l], e[idx] = r, w[idx] = x, h[l] = idx++;
}

int dijskra()
{
    memset(dis, 0x3f, sizeof dis);
    int ans = 0;
    dis[st] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    que.push({dis[st], st});
    while (!que.empty())
    {
        auto t = que.top();
        que.pop();
        int x = t.second, distance = t.first;
        if (use[x])
            continue;
        use[x] = true;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int j = e[i], wx = w[i];
            dis[j] = min(dis[j], distance + wx);
            que.push({dis[j], j});
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        ans = max(ans, dis[i]);
    }
    return ans;
}

int main()
{
    memset(h, -1, sizeof h);
    int m;
    cin >> n >> st >> m;
    while (m--)
    {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        add(l, r, x);
    }

    int res = dijskra();

    if (res >= INF)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", res);
    }

    return 0;
}

dijskra，看题的时候看错了以为要求所有路径的时间，算的是9答案写的5，看了半天才发现好像更简单 import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int m = sc.nextInt();
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int v = sc.nextInt();
            int u = sc.nextInt();
            int w = sc.nextInt();
            buildGraph(map, v, u, w);
        }
        int[] path = minPath(map, k, n);
        if(path[0]<n){
            System.out.println(-1);
            return;
        }
        int res = 0;
        for (int i = 1; i < path.length; i++) {
            if(i==k)continue;
            res = Math.max(path[i],res);
        }
        System.out.println(res);
    }

    private static int[] minPath(Map<Integer, List<int[]>> map, int k, int n) {
        boolean[] flag = new boolean[n+1];
        int count = 1;
        int[] res = new int[n+1];
        Arrays.fill(res,Integer.MAX_VALUE);
        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        q.offer(new int[]{k,0});
        while (!q.isEmpty()){
            int len = q.size();
            for (int i = 0; i < len; i++) {
                int[] poll = q.poll();
                List<int[]> ints = map.get(poll[0]);
                if(ints==null)continue;
                for (int[] anInt : ints) {
                    if(poll[1]+anInt[1]>res[anInt[0]])continue;
                    if(!flag[anInt[0]]){
                        count++;flag[anInt[0]] = true;
                    }
                    res[anInt[0]] = poll[1]+anInt[1];
                    q.offer(new int[]{anInt[0],poll[1]+anInt[1]});
                }
            }
        }
        res[0] = count;
        return res;
    }

    private static void buildGraph(Map<Integer, List<int[]>> map, int v, int u, int w) {
        List<int[]> ints = map.get(v);
        if(ints==null)
            ints = new ArrayList<>();
        ints.add(new int[]{u, w});
        map.put(v,ints);
    }
}

N,K,M=list(map(int,input().split(' ')))
Dist=[[float('inf') for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    v,u,w = list(map(int,input().split()))
    Dist[v][u]=w
def Dijkstra(a,n):
    pool=[i for i in range(1,n+1) if i!=a]
    cur,dist=a,Dist[a]
    while pool:
        tmp,cur=dist[pool[0]],pool[0]
        for des in pool:
            if dist[des]<tmp:  
                tmp,cur=dist[des],des
        pool.remove(cur)
        for des in pool:
            Dist[a][des]=min(Dist[a][des],Dist[cur][des]+Dist[a][cur])
    return max([Dist[a][i] for i in range(1,n+1) if i!=a])

res=Dijkstra(K,N)
res = -1 if res==float('inf') else res
print(res)