最小传输时延
标题：最小传输时延 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
某通信网络中有N个网络结点，用1到N进行标识。网络通过一个有向无环图表示，其中图的边的值表示结点之间的消息传递时延。
现给定相连节点之间的时延列表times[i]={u,v,w}，其中u表示源结点，v表示目的结点，w表示u和v之间的消息传递时延。请计算给定源结点到目的结点的最小传输时延，如果目的结点不可达，返回-1。
//package com.yang.Test;
import java.util.*;
/**
* 最小传输时延
* 输入
* 3 3
* 1 2 11
* 2 3 13
* 1 3 50
* 1 3
*/
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
Map<Integer,Map<Integer, List<Integer>>> routeMap = new TreeMap<>();
String firstLine = input.nextLine();
String[] overall = firstLine.split(" ");
int tableRows = Integer.parseInt(overall[1]);
for (int i = 0; i < tableRows; i++) {
String[] rowData = input.nextLine().split(" ");
if (!routeMap.containsKey(Integer.valueOf(rowData[0]))){
routeMap.put(Integer.valueOf(rowData[0]),new TreeMap<>());
}
Map<Integer,List<Integer>> routes = routeMap.get(Integer.valueOf(rowData[0]));
if (!routes.containsKey(Integer.valueOf(rowData[2]))){
routes.put(Integer.valueOf(rowData[2]),new ArrayList<>());
}
List<Integer> dests = routes.get(Integer.valueOf(rowData[2]));
dests.add(Integer.valueOf(rowData[1]));
routes.put(Integer.valueOf(rowData[2]),dests);
}
String[] question = input.nextLine().split(" ");
int origin = Integer.parseInt(question[0]),dest = Integer.parseInt(question[1]);
if (!routeMap.containsKey(origin)){
System.out.println(-1);
return;
}
Map<Integer, Integer> quickestRoute = new HashMap<>();
quickestRoute.put(origin, 0);
Stack<Integer> stack = new Stack<>();
stack.add(origin);
Set<Integer> visitedNode = new HashSet<>();
while (!stack.isEmpty()){
int current = stack.pop();
if (!routeMap.containsKey(current)){
continue;
}
for (Map.Entry<Integer, List<Integer>> entry : routeMap.get(current).entrySet()) {
Integer key = entry.getKey();
List<Integer> value = entry.getValue();
for (int node : value) {
if (!quickestRoute.containsKey(node)){
quickestRoute.put(node, Integer.MAX_VALUE);
}
int storedValue = quickestRoute.get(node);
if (storedValue > quickestRoute.get(current) + key){
quickestRoute.put(node, quickestRoute.get(current) + key);
visitedNode.remove(node);
}
if (!visitedNode.contains(node))
stack.add(node);
}
}
visitedNode.add(current);
}
if (!quickestRoute.containsKey(dest)) {
System.out.println(-1);
}else {
System.out.println(quickestRoute.get(dest));
}
}
}
查看14道真题和解析