Shortest paths in a graph

Plus

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 a_i and the vertex b_i at distance c_i. 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: a_i, b_i , c_i ( $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 a_{i vertices} and b_i and is c_i.
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 x_j to vertex y_j via vertex K.

Input
The first line contains an integer N ( $3<=N<=10^5$ ). The following N lines contain the vertices a_i and b_i ( $1<=a_i,b_i<=N$ , $1<=i<=N-1$ ) and the length between them c_i(\(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 x_j, y_j (,, < 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<=10⁵) and M (0<=M<=2*10⁵). Each of the next M lines contains 3 numbers: pi, qi and ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10⁶, 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