Maslaning qo’yilishi

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.Scanner;

public class EnQisqaYol {

static final double INF = 1e9;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int from = sc.nextInt();

int to = sc.nextInt();

double[][]a = new double[n][n];

double[]d = new double[n];

Arrays.fill(d, INF);

d[from] = 0;

int[]p = new int[n];

boolean[]used = new boolean[n];

for (int i = 1; i <= n; i++) {

int v = -1;

for (int j = 0; j < n; j++) {

if (!used[j] && (v==-1 || d[j] < d[v]))

v = j;

}

if (Math.abs(d[v]-INF) < 5) {

break;

}

used[v] = true;

for (int j = 0; j < n; j++) {

if (a[v][j] > 0 && d[v]+a[v][j] < d[j]) {

p[j] = v;

d[j] = d[v]+a[v][j];

}

}

}

ArrayList path = new ArrayList();

if (Math.abs(d[to]-INF) < 5) {

System.out.println("Yo'l mavjud emas");

}

else {

int cur = to;

while (true) {

path.add(cur+1);

if (cur==from)

break;

cur = p[cur];

}

Collections.reverse(path);

System.out.println(path);

}

}

}

1-Topshiriq

763. 64 MB

Given a connected weighted undirected graph.

    Consider a pair of vertices, the distance between which is maximum among all pairs of vertices. The distance between them is called the diameter of the graph. Eccentricity of vertex v is the maximum distance from a vertex v to the other vertices of the graph. Radius of a graph is the smallest of the eccentricities of the vertices.

    Find the diameter and radius of the graph.

Input

The first line of the input only number: N (1 ≤ N ≤ 100) - the number of vertices. The next N lines by N numbers - the adjacency matrix of the graph, where -1 means no edges between vertices, and any non-negative number - the presence of an edge weight. On the main diagonal of the matrix is always zero; weight edges do not exceed 1000.

Output

Output two numbers - the diameter and radius of the graph in separate lines.

Samples

№	Input	Output
1	4 0 -1 1 2 -1 0 -1 5 1 -1 0 4 2 5 4 0	8 5

2-Topshiriq Y2-o`nalis2h
limiti: 1 sekund
Xotira limiti: 64 MB

Shohruh o`qishdan tashqari juda ko`plab joylardai shlaydi. U yashayotgan joyda N ta shahar bo`lib, har bir shahardan qolgan hamma shaharga borsa bo`ladi. Shohruhning uyi V – shaharda joylashgan. U ertalab uyidan chiqishdan oldin boradigan joylarini ro`yxatini tuzadi. Uning ro`yxati bo`yicha u T ta joyga berilgan tartibda borishi kerak. Buning uchun u oldin X – shaharga borib kerakli narsalarni oladi va keyin Y – shaharga o`tadi. Shohruh vaqtni juda qadrlagani sabab rejadagi joylarni hammasiga minimal vaqtda borishni rejalashtirmoqda. Sizning vazifangiz Shohruh qancha vaqtini yo`lda o`tkazganini topishdan iborat.

Kiruvchima`luotlar

N – shaharlarsoni(1≤N≤100).

N x N lik matritsa orqali shaharlarning bog`lanishi beriladi. 0 bo`lsa bog`lanish yo`q. Aks holda ikki shahar orasidagi o`tish vaqti berilgan bo`ladi. Qiymati 10⁶ dan oshmaydi.

V – Shohruhning uyi joylashgan shahar

T(1≤T≤100) – Shohruhning rejalashtirgan joylari soni

Keyin T ta qatorda X va Y (1≤X,Y≤N)sonlar beriladi

Chiquvchi ma`lumotlar:

Shohruhning yo`lda yo`qotgan minimal vaqtini chiqaring

Kiruvchi ma`lumot	Chiquvchi ma`lumotlar
3 0 1 1 1 0 2 1 2 0 1 3 1 2 2 3 3 1	4

3-Topshiriq

Imagine yourself in a big city. You want to get from point A to point B. To do that you may move by foot or use the underground. Moving by the underground is faster but you may enter and exit it only at the stations. To save your time you decided to write a program to find the fastest route.

Input

The first line contains two floating point numbers. First of them is the speed of traveling by foot. The second one is the speed of traveling by the underground. The second speed is always greater than the first one.

Then description of the underground follows. It starts with an integer number N in the first line. It is the number of the underground stations. You may assume that N is not greater than 200. The following N lines contain two floating point numbers each (i-th line contains the coordinates of i-th station). Then the description of the connections between stations follows. Each connection is determined by the pair of integers, i.e. by the numbers of connected stations. The list of connections is terminates with a pair of zeroes. We assume that all the connections are straight. So the time we need to travel between stations is equal to the distance between stations divided by the speed of traveling by the underground.

It should be mentioned also that entering and exiting the underground and changing trains are possible at the stations only and takes no time.

At last the coordinates of the points A and B are given, tha pair of coordinates in a line.

Output

The first line should contain the minimal time needed to get from the point A to the point B. Time should be given with the precision of 10⁻⁶. The second line describes the use of the underground while traveling. It starts with the number of visited stations with tha following list of visited stations in the order they should be visited.

Sample

input	output
1 100 4 0 0 1 0 9 0 9 9 1 2 1 3 2 4 0 0 10 10 10 0	2.6346295 4 4 2 1 3

4-Topshiriq

The world is in danger! Awful earthquakes are detected all over the world. Houses are destroyed, rivers overflow the banks, it is almost impossible to move from one city to another. Some roads are still useful, but even they became too steep because of soil movements.

Fortunately, engineer Ivan has a car, which can go well uphill and downhill. But there are different gear-modes for movement up and down, so during the driving you have to change gear-modes all the time. Also engineer Ivan has a good friend –– geologist Orlov. Together they are able to invent a plan for world saving. But, unfortunately, geologist Orlov lives in another town.

Ivan wants to save the world, but gear-box in his car started to wear out, so he doesn’t know, how long he will be able to use it. Please help Ivan to save the world. Find a route to the Orlov's town, such that Ivan will have to change gear-modes as few times as possible. In the beginning of the way Ivan can turn on any of gear-modes and you don't have to count this action as a changing of gear-mode.

Input

There are two positive integer numbers n and m in the first line, the number of towns and roads between them respectively (2 ≤ n ≤ 10 000; 1 ≤ m ≤ 100 000). Next m lines contain two numbers each — numbers of towns, which are connected by road. Moreover, the first is the town, which is situated below, from which you should go uphill by this road. Every road can be used for traveling in any of two directions. There is at most one road between any two cities. In the last line there are numbers of two cities, in which Ivan and geologist Orlov live, respectively. Although the majority of roads were destroyed, Ivan knows exactly, that the way to geologist Orlov's city exists.

Output

Output the smallest number of gear-modes changes on the way to Orlov's city.

Samples

input	output
3 2 1 2 3 2 1 3	1
3 3 1 2 2 3 3 1 1 3	0