Shortest paths in a graph


Plus
Pin


Problem description Progress
ID 38521. Candidates for no shortcut
Темы: Algorithms on graphs    Shortest paths in a graph   

Given an undirected connected weighted graph with N vertices and M edges that contains neither loops nor double edges. I-e (\(1<=i<=M\)) edge connects vertex ai and the vertex bi at distance ci. We will assume that the loop is an edge, where \(a_i=b_i\) (\(1<=i<= M\)), and double edges are two edges where \((a_i,b_i)=(a_j,b_j) \) or \((a_i,b_i)=(b_j,a_j)\) (\(1<=i<j< ;=M\)). A connected graph is a graph in which there is a path between every pair of distinct vertices. Find the number of edges that do not belong to any shortest path between any pair of distinct vertices.< br />
Input
The first line specifies two integers N and M (\(2<=N<=100\) , \(N-1<=M<=min(N \cdot (N-1)/2,1000)\)). This is followed by M lines of three integers per line: ai, bi , ci (\(1<=a_i, b_i<=N\)< /span>, \(1<=c_i<=1000\)). This graph does not contain loops or double edges. This graph is connected .

Imprint
Print the number of edges in the graph that do not belong to any shortest path between any pair of distinct vertices.
 

 

Examples
# Input Output Explanations
1 
3 3
1 2 1
1 3 1
2 3 3

1
 In this graph, the shortest paths between all pairs of distinct vertices are:
Shortest path from node 1 to node 2: node 1 → vertex 2, path length is 1.
Shortest path from node 1 to node 3: node 1 → vertex 3, path length is 1.
Shortest path from node 2 to node 1: node 2 → vertex 1, path length is 1.
Shortest path from node 2 to node 3: node 2 → peak 1 → vertex 3, path length is 2.
Shortest path from node 3 to node 1: node 3 → vertex 1, path length is 1.
Shortest path from node 3 to node 2: node 3 → peak 1 → vertex 2, path length is 2.
So the only edge that is not contained in any shortest path is the edge of length 3 connecting vertex 2 and vertex 3, so the output should be 1.
2 
3 2
1 2 1
2 3 1

0
 Each edge is contained in some shortest path between a pair of distinct vertices.

 
ID 38585. transit route
Темы: Algorithms on graphs    Shortest paths in a graph    Bypass in width   

You are given a tree with N vertices. Here a tree is a kind of graph, more precisely, a connected undirected graph with N−1 edges, where N is the number of its vertices. Ith edge (\(1<=i<=N-1\)) connects ai vertices and bi and is ci.
You are also given Q queries and an integer K. For each jth query (\(1<=j<=Q\)) find the length of the shortest path from the top xj to vertex yj via vertex K.

Input
The first line contains an integer N (\(3<=N<=10^5\)). The following N lines contain the vertices ai and bi (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\) ) and the length between them ci (\(1<=c_i<=10^9\ ), \(1<=i<=N-1\))
Next come two numbers Q and K (\(1<=Q<=10^5\), \(1<=K<=N\)). The last Q lines contain integers xj, yj  (\(x_j \neq y_j\),\(x_j \neq K\), < span class="math-tex">\(y_j \neq K\) \(1<=j<=Q\), ) . 
The given graph is a tree.

Imprint
Print responses to queries in Q lines. On the j-th line print the answer to the j-th query.

 

Examples
# Input Output Explanation
1 5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
24
23
4 5		 3
2
4		 The shortest paths for the three queries are as follows:

Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4: Length 1 + 1 + 1 = 3
Query 2: Vertex 2 → Vertex 1 → Vertex 3: Length 1 + 1 = 2
Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Pinnacle 3 → Vertex 5: Length 1 + 1 + 1 + 1 = 4
2 7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7 		5
14
22		 The path for each request must pass through node K = 2.
3 10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10 		17000000000  

 
ID 38655. Metro Davilon
Темы: Algorithms on graphs    Shortest paths in a graph   

Davilon is the largest city on the moon. Davilon has its own metro system, consisting of N stations and M railway lines. The stations are numbered from 1 to N. Each line is operated by a company. Each company has an identification number. The ith (1<=i<=M) line connects station pi and qi bidirectionally. There is no intermediate station. This line is run by ci. You can transfer at stations where there are several lines available. The fare system used in this subway system is a bit odd. When a passenger uses only those lines operated by the same company, the fare is 1 santik (the currency of Davilon). Each time a passenger transfers to a line operated by a company other than the current line, the passenger will be charged an additional fare of 1 centik. In the event that a passenger who switched from the line of company A to the line of another company switches again to the line of company A, the additional fare is charged again. Dunno is now at station 1 and wants to get to station N by metro. Find the minimum required rate.

Input
The first line contains two integers N (2<=N<=105) and M (0<=M<=2*105). Each of the next M lines contains 3 numbers: pi, qi and ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=106, pi ≠ qi. 

Imprint
Output the minimum required rate. If it is impossible to get to station N by metro, print -1.

 

Examples
# Input Output Explanation
1 3 3
1 2 1
2 3 1
3 1 2 		1 Use company lines 1:
1 &rr; 2 &rr; 3.
The fare is 1 cent.
2 8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5 		2 Use company lines first:
1 &rr; 3 &rr; 2 &rr; 5 &rr; 6.
Then use company lines 5:
6 &rr; 7 &rr; 8.
The fare is 2 cents.
3 2 0 -1