问题描述
试题编号： 201609-4 试题名称： 交通规划 时间限制： 1.0s 内存限制： 256.0MB 问题描述：
问题描述
G国国王来中国参观后，被中国的高速铁路深深的震撼，决定为自己的国家也建设一个高速铁路系统。
建设高速铁路投入非常大，为了节约建设成本，G国国王决定不新建铁路，而是将已有的铁路改造成高速铁路。现在，请你为G国国王提供一个方案，将现有的一部分铁路改造成高速铁路，使得任何两个城市间都可以通过高速铁路到达，而且从所有城市乘坐高速铁路到首都的最短路程和原来一样长。请你告诉G国国王在这些条件下最少要改造多长的铁路。
输入格式
输入的第一行包含两个整数n, m，分别表示G国城市的数量和城市间铁路的数量。所有的城市由1到n编号，首都为1号。
接下来m行，每行三个整数a, b, c，表示城市a和城市b之间有一条长度为c的双向铁路。这条铁路不会经过a和b以外的城市。
输出格式
输出一行，表示在满足条件的情况下最少要改造的铁路长度。
样例输入
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2
样例输出
11
评测用例规模与约定
对于20%的评测用例，1 ≤ n ≤ 10，1 ≤ m ≤ 50；
对于50%的评测用例，1 ≤ n ≤ 100，1 ≤ m ≤ 5000；
对于80%的评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 50000；
对于100%的评测用例，1 ≤ n ≤ 10000，1 ≤ m ≤ 100000，1 ≤ a, b ≤ n，1 ≤ c ≤ 1000。输入保证每个城市都可以通过铁路达到首都。
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;
import java.util.concurrent.ArrayBlockingQueue;
import javax.swing.text.html.MinimalHTMLWriter;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int INT_MAX=1000;
int v=scanner.nextInt();
int[] dist=new int[v+1];
int[] cost=new int[v+1];
for (int i = 1; i <=v; i++) {
dist[i]=INT_MAX;
cost[i]=INT_MAX;
}
int e=scanner.nextInt();
Graph graph=new Graph(v, e);
for (int i = 1; i <=v; i++) {
graph.adjlist[i]=new node(i);
}
for (int i = 0; i < e; i++) {
int src=scanner.nextInt();
int des=scanner.nextInt();
int cost1=scanner.nextInt();
edge edge1=new edge(src, cost1);
edge edge2=new edge(des, cost1);
graph.adjlist[src].list.add(edge2);
graph.adjlist[des].list.add(edge1);
}
digkstra_add(1,v,graph,dist,cost);
int ans=0;
for (int i = 1; i <=v; i++) {
ans+=cost[i];
}
System.out.println(ans);
}
public static void digkstra_add(int start,int n,Graph graph,int[] dist,int[] cost){
Queue<node> queue=new ArrayBlockingQueue<>(n);
node startNode=graph.adjlist[start];
queue.add(startNode);
int[] visited=new int[n+1];
dist[start]=0;
cost[start]=0;
while (!queue.isEmpty()) {
node vNode=queue.peek();
queue.remove();
while (visited[vNode.v]!=1) {
visited[vNode.v]=1;
for (edge e:graph.adjlist[vNode.v].list) {
int v2=e.v;
if (visited[v2]==1) {
continue;
}
int tempcost=e.cost;
int nextdist=dist[vNode.v]+tempcost;
if (dist[v2]>nextdist) {
dist[v2]=nextdist;
cost[v2]=tempcost;
queue.add(graph.adjlist[v2]);
}else if (dist[v2]==nextdist) {
cost[v2]=Math.min(cost[v2], tempcost);
}
}
}
}
}
}
class node{
int v;
List<edge> list;
public node(int v1) {
v=v1;
list=new ArrayList<edge>();
}
}
class edge{
int v;
int cost;
public edge(int v2,int cost2) {
v=v2;
cost=cost2;
}
}
class Graph{
int vnum;
int rnum;
node[] adjlist;
public Graph(int v,int e) {
vnum=v;
rnum=e;
adjlist=new node[v+1];
}
}
结果是出来的了，错误就不知道是哪里了，现在做出的题竟然没有一个完整的。
使用的算法是dijistra求单源最短路径的算法，使用一个数组放置单源的最短路径，再使用一个数组放置从首都到当前结点所需要增加的最短路径的长度，即最小花费。
确定到所有点需要增加的路线的花费之后，相加得出修建所有路径的最小花费，即为所求。
