Problem Description
| Question number: | 201609-4 |
| Test Name: | traffic planning |
| Time limit: | 1.0s |
| Memory limit: | 256.0MB |
| Description of the problem: |
Problem Description
After his visit to China, King G was deeply shocked by China's high-speed railways and decided to build a high-speed railway system for his country.
The construction of high-speed railways is very costly. In order to save construction costs, the King of G decided not to build new railways, but to transform existing railways into high-speed railways.Now, you will provide King G with a plan to transform some of the existing railways into high-speed railways so that any two cities can be reached by high-speed railways, and the shortest route from all cities to the capital by high-speed railways is as long as it used to be.Please tell King G how long the railways should be rebuilt under these conditions at least. Input Format
The first line of input contains two integers, n and m, representing the number of cities in G and the number of inter-city railways, respectively.All cities are numbered from 1 to n and the capital is No. 1.
The next m lines, each with three integers a, b, c, indicate that there is a two-way railway with a length of C between city a and city B.This railway will not pass through cities other than a and B. Output Format
The output line represents the minimum length of the railroad to be transformed if the conditions are met.
sample input
4 5
1 2 4 1 3 5 2 3 2 2 4 3 3 4 2 sample output
11
Measure use case size and conventions
For 20% of the test cases, 1 < n < 10, 1 < m < 50;
For 50% of the test cases, 1 < n < 100, 1 < m < 5000; For 80% of the test cases, 1 < n < 1000, 1 < m < 50000; For 100% of the evaluation cases, 1 < n < 10000, 1 < m < 100000, 1 < a, b < n, 1 < c < < 1000.The input ensures that each city can reach the capital by rail. |
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main1 {
static int INT_MAX=10000;
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int v=scanner.nextInt();
int e=scanner.nextInt();
Vex[] vex=new Vex[v+1];
for (int i = 1; i <= v; i++) {
vex[i]=new Vex();
}
for (int i = 0; i < e; i++) {
int from=scanner.nextInt();
int to=scanner.nextInt();
int cost=scanner.nextInt();
Edge edge=new Edge(to, cost);
vex[from].edges.add(edge);
edge=new Edge(from, cost);
vex[to].edges.add(edge);
}
int cost=dijkstra(1,vex,v);
System.out.println(cost);
}
public static int dijkstra(int start,Vex[] vex,int v){
int lowcost=0;
int[] visited=new int[v+1];
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;
}
dist[start]=0;
cost[start]=0;
Queue<Integer> queue=new ArrayDeque<>();
queue.add(start);
while (!queue.isEmpty()) {
int node=queue.poll();
while (visited[node]!=1) {
visited[node]=1;
for (Edge edge : vex[node].edges) {
int to=edge.to;
if (visited[to]==1) {
continue;
}
int tempcost=edge.cost;
int tempdist=dist[node]+tempcost;
if (tempdist<dist[to]) {
dist[to]=tempdist;
cost[to]=tempcost;
queue.add(to);
}else if (tempdist==dist[to]) {
if (tempcost<cost[to]) {
cost[to]=tempcost;
}
}
}
}
}
for (int i = 2; i <=v; i++) {
lowcost=lowcost+cost[i];
}
return lowcost;
}
}
class Vex{
List<Edge> edges;
public Vex(){
edges=new ArrayList<Edge>();
}
}
class Edge{
int to;
int cost;
public Edge(int t,int c){
to=t;
cost=c;
}
}