| Problem description | | Progress |
|
Темы:
Ford-Bellman algorithm
In a directed weighted graph, the vertices are numbered from 1 to n. If i<j, then there is an edge from vertex i to vertex j whose weight is determined by the formula \(wt(i,j)=(179i+719j)\ mod \ 1000 - 500 \). Determine the weight of the shortest path leading from vertex 1 to vertex n.
Input:
The program receives a single number n (2≤n≤13000) as input.
Output:
The program should output a single integer - the weight of the shortest path from vertex 1 to vertex n in the described column.
Examples
| # |
Input |
Output |
| 1 |
2 |
117 |
| 2 |
3 |
-164 |
| |
![]()
|
|
Темы:
Ford-Bellman algorithm
Attraction "Labyrinth of Knowledge" was built at the Summer Computer School (LCS). The labyrinth consists of N rooms, numbered from 1 to N, some of which have doors between them. When a person passes through a door, the indicator of his knowledge changes by a certain amount fixed for this door. The entrance to the labyrinth is in room 1, the exit – in room N. Each student goes through the maze exactly once and gets into one or another study group depending on the amount of knowledge gained (when entering the maze, this indicator is zero). Your task is to show the best result.
Input:
The first line of the input contains integers N (1 <= N <= 2000) – number of rooms and M (1 <= M <= 10000) – Number of doors. Each of the next M lines contains a description of the door – the numbers of the rooms from which it leads and to which it leads (you can only walk through the door in one direction), as well as an integer that is added to the amount of knowledge when passing through the door (this number does not exceed 10000 in modulo). Doors can lead from a room to itself, there can be more than one door between two rooms.
Output:
Display ":)" – if you can get an unlimited amount of knowledge, ":(" – if the labyrinth cannot be passed, and the maximum amount of knowledge gained otherwise.
Examples
| # |
Input |
Output |
| 1 |
2 2
1 2 3
1 2 7
|
7 |
| |
![]()
|
|
Темы:
Ford-Bellman algorithm
Given a directed graph that can have multiple edges and loops. Each edge has a weight expressed as an integer (possibly negative). It is guaranteed that there are no negative weight cycles.
You need to calculate the lengths of the shortest paths from vertex number 1 to all other vertices.
Input
The program first receives the number N (1 <= N <= 100) – the number of graph vertices and the number M (0 <= M <= 10000) – number of ribs. The following lines contain M triples of numbers describing the edges: the beginning of the edge, the end of the edge, and the weight (the weight – is an integer from -100 to 100).
Output
The program should output N numbers – distances from vertex number 1 to all vertices of the graph. If there is no path to the corresponding vertex, print the number 30000 instead of the length of the path.
Examples
| # |
Input |
Output |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |
| |
![]()
|
|
Темы:
Ford-Bellman algorithm
Given a directed weighted graph with negative edges (no negative cycles).
Given a start and end vertex, define the minimum distance between them.
Input:
Given 4 numbers n, m, s, f - number of vertices, number of edges, start and end vertex (starting from 1), respectively.
The next m lines contain 3 numbers each - vertex 1, vertex 2 and the price of transition between vertices.
Output:
It is required to display one number - the answer to the task. If there is no answer, output Inf.
Examples
| # |
Input |
Output |
| 1 |
4 2 1 4
1 2 100500
2 3 100500
|
Inf |
| |
![]()
|
|
Темы:
Ford-Bellman algorithm
A weighted directed graph is given. It is required to determine whether it contains a cycle of negative weight. It is guaranteed that all vertices of the graph are reachable from the first one.
Input:
The first line of the input file contains two natural numbers n and m — the number of vertices and edges of the graph respectively ( n ≤ 1 111, m ≤ 11 111).
The next m lines contain the description of the edges, one per line. Edge number i is described by three numbers bi, ei and wi — the numbers of the ends of the rib and its weight, respectively (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000). Note that the graph can have multiple edges and loops.
Output:
The first line of the output file should contain yes if the graph contains a cycle of negative weight and no — otherwise.
Examples
| # |
Input |
Output |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| yes |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| no |
| |
![]()
|
|
Темы:
Ford-Bellman algorithm
Complete the program so that it correctly solves the following problem.
Given a directed graph that can have multiple edges and loops. Each edge has a weight expressed as an integer (possibly negative). It is guaranteed that there are no negative weight cycles.
You need to calculate the lengths of the shortest paths from vertex number 1 to all other vertices.
Input
The program first receives the number N (1 <= N <= 100) – the number of graph vertices and the number M (0 <= M <= 10000) – number of ribs. The following lines contain M of triples of numbers describing the edges: the beginning of the edge, the end of the edge, and the weight (weight – is an integer from -100 to 100).
Output
The program should output N numbers – distances from vertex number 1 to all vertices of the graph. If there is no path to the corresponding vertex, print the number 30000 instead of the length of the path.
Examples
| # |
Input |
Output |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |
| |
![]()
|