0-1 BFS

Plus

Problem description Progress

ID 21770. 1-k BFS

You are given a directed weighted graph. You need to find the distance from the top 1 to all the others, using the algorithm 1 - k BFS.

Input
The first line contains 2 integers n and m, the number of vertices and edges in the graph, respectively. The following m lines contain 3 numbers each a and b - the vertices that the edge connects and c - the weight of this edge (a, b, c >= 0).

Output
It is necessary to output n-1 number separated by a space - the distances from the top 1 to all the others, if there is no possible path from 1 to i< /code> vertex, then you need to output Impossible.


 

 

Examples




#
Input
Output




1

9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100


1 4 3 6 4 Impossible Impossible Impossible

ID 33469. *Stalker

Темы: 0-1 BFS Dec

In the city of N, under unclear circumstances, the territory of one of the factories turned into an anomalous zone. All entrances to the territory were blocked, and it itself was called the industrial zone. There are N buildings in the industrial zone, some of them are connected by roads. Any road can be traveled in both directions.
The novice stalker was given the task to get to the warehouse in the industrial zone. He found several maps of the territory of the industrial zone in the electronic archive. Since the maps were compiled by different people, each of them contains information only about some roads of the industrial zone. The same road can appear on several maps.
On the way, the stalker can download one card from the archive to the mobile phone. When you download a new map, the previous one is not stored in the phone's memory. The stalker can only move along the roads marked on the currently loaded map. Each map download costs 1 ruble. To minimize costs, the stalker needs to choose such a route in order to download maps as few times as possible. Stalker can download the same map several times, and you will have to pay for each download. Initially, there is no card in the mobile phone's memory.

It is required to write a program that calculates the minimum amount of expenses necessary for a stalker to get from the entrance to the industrial zone to the warehouse.

Input:
- the first line of the input contains two natural numbers N and K (\(2 <= N <= 2000\ ); \(1 <= K <= 2000\)) — the number of industrial zone buildings and the number of maps, respectively. The entrance to the industrial zone is located in the building with the number 1, and the warehouse — in building number N.
- in the following lines there is information about the available cards. The first line of the description of the ith card contains the number r_i — number of roads marked on the i-th map;
- then come r_i strings containing two natural numbers a and b (\(1 <= a\), \(b <= N\); \(a ? b\)), meaning that there is a road on the i-th map connecting buildings a and b. The total number of roads marked on all maps does not exceed 300,000 (\(r_1 + r_2 + … + r_K <= 300,000\)). Output: print a single number — the minimum amount of the stalker's expenses. If it is impossible to get to the warehouse, print the number –1.

ID 33468. 0-1 BFS: Beginning (C++)

Темы: 0-1 BFS

Given an image of an undirected graph (has edges of weight 0 and 1), print a list of the shortest distances from vertex 0 to all others.

Input
An image of an undirected graph with edges 0 and 1 is given.

Output
In your answer, output a list of shortest paths from vertex 0.