网易严选建有N个自营仓分布在全国各地,标记为仓库1到N。
给定一个配货时间组(v,u,w),v为出发仓库,u为目标仓库,w为从出发仓库到目标仓库的耗时时间。可能存在仓库间过远,无法支持调拨转货。
指定一个出发仓库K,我们需要将供应商发送到K仓库的货配送到各个仓库。问配送到所有可到达仓库所要最短时间?如果无法全部调拨到,则返回-1.
进阶:时间复杂度,空间复杂度
第一行三个正整数,由空格分割,分别表示仓库个数N,出发仓K,以及配送时间组个数M接下来 M行,每行三个整数,由空格分割,分别表示(v,u,w)三个数,v为出发仓库,u为目标仓库,w为从出发仓库到目标仓库的耗时时间1<=N<=301<=K<=N1<=M<=1301<=u,v<=N1<=w<=20
一行一个数字表示答案,配送到所有可达仓库到最短时间
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
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))
懒得写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.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(); } }
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); } } }
贴一个堆优化的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);
}
}
#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; }提交观点
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邻接矩阵实现,实际本题偏稀疏矩阵应可用邻接表加速。
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))