| Problem description | | Progress |
|
Темы:
Dijkstra's algorithm
You are given a directed weighted graph. Find the shortest path from one given vertex to another.
Input
The first line contains three numbers: N, S and F (1≤N≤100, 1≤S, F≤N), where N – number of graph vertices, S – initial vertex, and F – final. In the next N lines, enter N numbers each, not exceeding 100, – graph adjacency matrix, where -1 means no edge between vertices, and any non-negative number – the presence of an edge of given weight. Zeros are written on the main diagonal of the matrix.
Output
It is required to display sequentially all the vertices of one (any) of the shortest paths, or one number -1 if there is no path between the specified vertices.
Examples
| # |
Input |
Output |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
There are N cities in the country, some of which are connected by roads. It takes one tank of gasoline to drive on one road. In addition, you have a gas canister that holds the same amount of fuel as a gas tank.
In each city, a tank of gasoline has a different cost. You need to get from the first city to the Nth one, spending as little money as possible.
In each city, you can fill up the tank, fill the tank and the canister, or pour gasoline from the canister into the tank. This allows you to save money by buying gasoline in those cities where it is cheaper, but the canister is only enough for one tank filling!
Input
The first line contains the number N (1<=N<=100), the next line contains N numbers, the i-th of which sets the cost of gasoline in the i-th city (all these are integers from the range from 0 to 100 ). Then comes the number M – the number of roads in the country, followed by a description of the roads themselves. Each road is given by two numbers – the numbers of the cities it connects. All roads are two-way (that is, they can be driven both in one direction and in the other direction), there is always no more than one road between two cities, there are no roads leading from the city to itself.
Output
Required to output a single number – the total cost of the route, or -1 if it's impossible to get there.
Examples
| # |
Input |
Output |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
One of the teams participating in the Olympiad decided to return home by train. At the same time, the guys want to get home as soon as possible. Unfortunately, not all electric trains go from the city where the Olympiad is held to the station where the guys live. And, what is even more offensive, not all electric trains that go past their station stop at it (as well as in general, electric trains do not stop at all the stations they pass by).
All stations on the line are numbered from 1 to N. At the same time, station number 1 is located in the city where the Olympiad is held, and at time 0 the guys arrive at the station. The station that the guys need to get to has the number E.
Write a program that, given a train schedule, calculates the minimum time when the guys can be at home.
Input
In the input file the numbers N (2 ≤ N ≤ 100) and E (2 ≤ E ≤ N) are written first. Then the number M (0 ≤ M ≤ 100) is written, indicating the number of train runs. The following is a description of M trips of electric trains. The description of each train flight begins with the number Ki (2 ≤ Ki ≤ N) — the number of stations it stops at, followed by Ki pairs of numbers, the first number of each pair specifies the station number, the second — time when the train stops at this station (time is expressed as an integer from 0 to 109). Stations within the same flight are ordered in ascending order of time. During one trip, the train moves in the same direction all the time — either away from the city or towards the city.
Output
To output file print one number — the minimum time when the guys can be at their station. If they can't get there by existing train routes, print –1.
Examples
| # |
Input |
Output |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
Напишите программу, которая будет находить расстояния в неориентированном взвешенном графе с неотрицательными длинами ребер, от указанной вершины до всех остальных. Программа должна работать быстро для больших разреженных графов.
Входные данные
В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.
Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.
Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.
Выходные данные
Выведите на стандартный выход (экран) NUM строк, в каждой из которых по Ni чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).
| Ввод |
Вывод |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
You are given a description of the country's road network. Your task – find the length of the shortest path between cities A and B.
Input
The road network is given in the input file as follows: the first line contains the numbers N and K (1<=N<=100000, 0<=K<=300000), where K – number of roads. Each of the following K lines contains a description of a two-way road – three integers ai, bi and li (1aibiN, 1li106). This means that there is a road of length li that leads from city ai to city bi. The last line contains two numbers A and B – numbers of cities between which it is necessary to calculate the shortest distance (1<=A,B<=N )
Imprint
You must output the single number – distance between required cities. If it is impossible to get from city A to city B by road, print –1.
Examples
| # |
Input |
Output |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
The government of some well-known country decided to globally rebuild the road system – it has already managed to destroy all the roads, and now it is necessary to rebuild the road network. New two-way roads can be built between any two cities, and the cost to build the road is equal to the distance between the respective cities. However, in some cases, the terrain allows you to build a road for a different price, such pairs of cities are called special. The government decided first of all to connect the two main cities of this country – A and B. You were instructed to develop a plan for the construction of roads, in which the total cost of all constructed roads will be as low as possible, and at the same time, along the constructed roads, it will be possible to get from city A to city B.
Input
The first line contains the number N – number of cities in the country (\(1\leq N\leq10^4\)). Each of the following N lines contains two integers, xi and yi – coordinates of the corresponding city (\(|x|, |y| \leq 10^6\) ). The following contains the number M – number of special pairs of cities (\(0\leq M \leq min(10^4, N(N-1)/2)\). Next M lines contain a description of special roads, each consisting of three integers: u, v – a pair of different cities between which the special road passes, and w – the cost of building the corresponding road (\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)).The last line contains the numbers of cities A and B (from 1 to N).
Imprint
Print one number – desired minimum length. Your answer should differ from the correct one by no more than 10−5.
Examples
| # |
Input |
Output |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
Binary search by answer
For the next Summer Computer School, it was decided to prepare circles for both schoolchildren and all teachers.
Having a habit of doing important things at the very last moment, the designer finished the layout two days before school started. It will take another day for the manufacturer to make mugs and put an image on them. It only takes 24 hours for NATO to take the mugs from the factory to LKSH.
An order for 10,000,000 mugs (namely, that's how many the organizers ordered), of course, cannot be taken away in one flight. However, for the first flight I want to bring the maximum number of mugs. One heavy truck was ordered for transportation. But there is one caveat: on some roads there is a limit on the weight of the car. Therefore, if the car is loaded with mugs to the eyeballs, then it may not be possible to use the shortest route, but you will have to take a detour. It may even happen that because of this, the truck will not have time to reach the camp on time, and this cannot be allowed. So, how many mugs can be loaded into the car in order to have time to bring this valuable cargo on time, and without violating the rules of the road?
Input
The first line contains the numbers n (1≤n≤500) and m - the number of nodes in the road map and the number of roads, respectively. The next m lines contain information about the roads. Each road is described on a separate line as follows. First, the numbers of the junction points that are connected by this road are given, then the time it takes to travel along this road, and finally, the maximum weight of a car that is allowed to drive on this road. It is known that all roads connect different points, and for each pair of points there is at most one road directly connecting them. All numbers are separated by one or more spaces.
Nodal points are numbered from 1 to n. At the same time, the plant for the production of mugs has number 1, and LKSH - number n. Travel time on the road is given in minutes and does not exceed 1440 (24 hours). The mass limit is given in grams and does not exceed one billion. In addition, it is known that one mug weighs 100 grams, and an empty truck - 3 tons.
Output
Print a single number - the maximum number of mugs that can be brought on the first flight, spending no more than 24 hours.
Examples
| # |
Input |
Output |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
In light of recent wiretapping news, the two hardline internet giants Uragania Laim.UR and "Xenda" decided to sign an agreement on establishing a secure communication channel between each other's data centers. There are n cities in Uragania, but, unfortunately, there are no data centers of both giants in any city. Therefore, to form a secure channel, long-distance communication lines will have to be laid.
The specialists of the companies have identified m pairs of cities that can be connected by laying a communication channel segment and estimated the cost of creating such a segment for each of these pairs.
The resulting channel may consist of several segments. It must start in one of the cities where the data center of the first company is located, it can pass through intermediate cities and must end in the city where the data center of the second company is located.
Now it is necessary to determine the minimum cost of a secure channel connecting two companies' data centers.
Input:
The first line contains integers n and m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 105 ) — the number of cities and the number of pairs of cities that can be connected by a link segment. The second line contains n integers ai (0 ≤ ai ≤ 2). If ai = 0, then there is no data center of any of the giants in the i-th city. If ai = 1, then the "Laim.UR" data center is located in the i-th city, and if ai = 2, then the "Xenda" data center is located in the i-th city; . It is guaranteed that among these numbers there is at least one one and one two. Each of the next m lines contains three integers — si , ti and ci , which means that the cities si and ti (1 ≤ si , ti ≤ n, si != ti< /sub>) can be connected by a link segment of cost ci (1 ≤ ci ≤ 105 ). Each pair of cities can be connected by at most one channel segment.
Output:
If it is possible to connect two data centers of different Internet giants with a secure communication channel, then print three numbers in the output file: x, y and d, meaning that it is possible to establish a communication channel between cities x and y with a total cost of d. In city x there should be a data center "Laim.UR", in city y — data center «Xenda». If there are several optimal answers, print any one. If it is impossible to draw the required channel, print −1.
Examples
| # |
Input |
Output |
| 1 |
6 7
1 0 1 2 2 0
1 3 3
1 2 4
2 3 3
2 4 2
1 6 5
3 5 6
5 6 1
| 3 4 5 |
| 2 |
4 2
1 0 0 2
1 3 3
2 4 2
| -1 |
Explanation
In the first example, it is optimal to build a communication channel from two segments: 3 − 2 and 2 .minus; 4.
| |
![]()
|
|
Темы:
Dijkstra's algorithm
You are given a directed weighted graph. Find the shortest distance from one given vertex to another.
Input
The first line contains three numbers: N, S and F (1≤ N≤ 100, 1≤ S, F≤ N), where N – number of graph vertices, S – initial vertex, and F – final. In the next N lines, enter N numbers each, not exceeding 100, – graph adjacency matrix, where -1 means no edge between vertices, and any non-negative number – the presence of an edge of given weight. Zeros are written on the main diagonal of the matrix.
Output
It is required to display the desired distance or -1 if there is no path between the specified vertices.
Examples
| # |
Input |
Output |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
3 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
There are N cities in the country, some of which are connected by roads. It takes one tank of gasoline to drive on one road. In each city, a tank of gasoline has a different cost. You need to get from the first city to the Nth one, spending as little money as possible. You can’t buy gasoline for future use.
Input
The first line contains the number N (1≤N≤100), the next line contains N numbers, the i-th of which specifies the cost of gasoline in the i-th city (these are integers from 0 to 100). Then comes the number M – the number of roads in the country, followed by a description of the roads themselves. Each road is given by two numbers – the numbers of the cities it connects. All roads are two-way (that is, they can be driven both in one direction and in the other direction), there is always no more than one road between two cities, there are no roads leading from the city to itself.
Output
Required to output a single number – the total cost of the route or -1 if it's impossible to get there.
Examples
| # |
Input |
Output |
| 1 |
5
3 6 1 7 6
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
|
3 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
There are buses between some villages in the Vasyuki region. Since the passenger traffic here is not very large, the buses run only a few times a day.
Maria Ivanovna needs to get from village d to village v as quickly as possible (she is considered to be in village d at time 0).
Input
First enter the number N – total number of villages (1 <= N <= 100), then the village numbers d and v, followed by the number of bus trips R (0 <= R <= 10000). The following are descriptions of bus routes. Each flight is given by the departure village number, departure time, destination village and arrival time (all times – are integers from 0 to 10000). If at time t a passenger arrives at some village, then he can leave it at any time starting from t.
Output
Print the minimum time when Maria Ivanovna can be in the village v. If she can't get from d to v using the given bus routes, print -1.
Examples
| # |
Input |
Output |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |
| |
![]()
|