首页 > 试题广场 >

仓库配送

[编程题]仓库配送
  • 热度指数:1831 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
网易严选建有N个自营仓分布在全国各地,标记为仓库1到N。
给定一个配货时间组(v,u,w),v为出发仓库,u为目标仓库,w为从出发仓库到目标仓库的耗时时间。可能存在仓库间过远,无法支持调拨转货。
指定一个出发仓库K,我们需要将供应商发送到K仓库的货配送到各个仓库。问配送到所有可到达仓库所要最短时间?如果无法全部调拨到,则返回-1.

进阶:时间复杂度,空间复杂度

输入描述:
第一行三个正整数,由空格分割,分别表示仓库个数N,出发仓K,以及配送时间组个数M
接下来 M行,每行三个整数,由空格分割,分别表示(v,u,w)三个数,v为出发仓库,u为目标仓库,w为从出发仓库到目标仓库的耗时时间
1<=N<=30
1<=K<=N
1<=M<=130
1<=u,v<=N
1<=w<=20


输出描述:
一行一个数字表示答案,配送到所有可达仓库到最短时间
示例1

输入

6 2 5
2 1 1
2 6 2
1 3 3
3 4 1
6 5 2

输出

5

说明

由图可知,所需最短时间为1+3+1=5

备注:
N的区间是[1, 100] ;
K的区间是[1, N] ;
times的最大长度是[1, 6000] ;
所有边 times[i] = (u, v, w),1<=u, v <= N 0 <= w <= 100
写一个python版本的最短路径
def solution(start, graph, N):
    passed = [start]
    nopass = [x for x in range(1, N + 1) if x != start]
    dis = graph[start]
    
    while len(nopass):
        idx = nopass[0]
                # 选出距离起点最近的点
        for i in nopass:
            if dis[i] < dis[idx]:
                idx = i
        nopass.remove(idx)
        passed.append(idx)
                # 更新距离
        for i in nopass:
            if dis[i] > dis[idx] + graph[idx][i]:
                dis[i] = dis[idx] + graph[idx][i]
    return max(dis[1:]) if max(dis[1:]) != float("inf") else -1

N, K, M = input().strip().split(' ')
N, K, M = int(N), int(K), int(M)
graph = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    graph[i][i] = 0
for _ in range(M):
    s, t, d = input().strip().split(' ')
    s, t, d = int(s), int(t), int(d)
    graph[s][t] = min(d, graph[s][t])
print(solution(K, graph, N))


发表于 2021-01-05 21:50:27 回复(0)

懒得写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;
}
发表于 2021-01-03 18:36:57 回复(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);
    }
}
发表于 2022-02-10 17:48:21 回复(0)


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();
            int[][] map = new int [N + 1][N + 1];
            int[] nodes = new int[N + 1];
            Boolean[] used = new Boolean[N + 1];
            for (int i = 0; i < N + 1; i++) 
            {
                Arrays.fill(map[i], -1);
                Arrays.fill(nodes, Integer.MAX_VALUE);
                Arrays.fill(used, false);
            }
            nodes[K] = 0; 
            for (int i = 0; i < M; i++) 
            {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int value = sc.nextInt();
                map[x][y] = value;
            }
            Dijskra(K, map, nodes, used, N);
            Boolean flag = false;
            for (int i = 1; i <= N; i++) 
            {
                if(used[i] == false)
                {
                    flag = true;
                    break;
                }
            }
            if(flag == true)
            {
                System.out.println(-1);
            }
            else
            {

                int max = 0;
                for (int i = 1; i <= N; i++) 
                {
                    if(nodes[i]>max)
                        max = nodes[i];
                }
                System.out.println(max);
                
            }
            
        }
    public static void Dijskra(int x, int[][] map, int[] nodes, Boolean[] used, int N)
    {
        if(x == -1)
            return;
        used[x] = true;
        for (int i = 1; i <= N; i++) 
        {
            if(map[x][i] != -1)
            {
     
                if(nodes[i] > nodes[x] + map[x][i])
                    nodes[i] = nodes[x] + map[x][i];
            }
        }

        int minpos = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= N; i++) 
        {
            if(used[i] == false && nodes[i] < min)
            {
                minpos = i;
                min = nodes[i];
            }
        }
        Dijskra(minpos, map, nodes, used, N);
    }

}

发表于 2021-04-29 17:47:41 回复(0)
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();
    }
}

发表于 2022-08-19 21:11:13 回复(0)
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);
        }
    }
}

发表于 2022-07-25 22:37:34 回复(0)
贴一个堆优化的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;
}


发表于 2022-04-07 10:11:38 回复(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);
    }
}

发表于 2022-03-29 20:12:24 回复(0)
堆优化dij nlogm
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
int n,k,m;
vector<pii>g[40];
int maxn=0x3f3f3f;
int dis[40];
int vis[40];
int main(){
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
   cin>>n>>k>>m;
   for(int i=0;i<m;i++){
       int u,v,w;
       cin>>u>>v>>w;
       g[u].push_back({v,w});
   }
   
    priority_queue<pii,vector<pii>,greater<pii> >q;
    dis[k]=0;
    q.push({0,k});
    while(!q.empty()){
        int u=q.top().second;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto x:g[u]){
            int v=x.first;
            if(vis[v])continue;
            if(dis[v]>dis[u]+x.second){
                dis[v]=dis[u]+x.second;
                q.push({dis[v],v});
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        if(dis[i]==0x3f3f3f3f){
            cout<<-1<<endl;
            return 0;
        }
        res=max(res,dis[i]);
    }
    cout<<res<<endl;
}
提交观点

发表于 2022-03-24 21:21:22 回复(0)
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)
python3 Dijkstra邻接矩阵实现,实际本题偏稀疏矩阵应可用邻接表加速。
发表于 2021-03-23 14:45:33 回复(0)
什么踏马的是模板题,翻译翻译什么踏马的叫踏马的模板题
import heapq

def readToInt():
    return [int(n) for n in input().split()]

NKM = readToInt()
graph = [set() for _ in range(NKM[0])]
for _ in range(NKM[2]):
    line = readToInt()
    v, u, w = line[0] - 1, line[1] - 1, line[2]
    graph[v].add((u, w))

def solve(graph, K):
    visisted = set()
    h = [(0, K)]
    ans = 0
    while len(h) != 0:
        time, v = heapq.heappop(h)
        if v in visisted:
            continue
        visisted.add(v)
        ans = time
        for u, w in graph[v]:
            if u not in visisted:
                heapq.heappush(h, (time + w, u))
    if len(visisted) == len(graph):
        return ans
    return -1

print(solve(graph, NKM[1] - 1))


发表于 2021-01-21 11:48:36 回复(0)