Maslaning qo’yilishi


import java.util.ArrayList; import



Download 109,5 Kb.
bet2/3
Sana31.12.2021
Hajmi109,5 Kb.
#232033
1   2   3
Bog'liq
4-misol

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);

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



Download 109,5 Kb.

Do'stlaringiz bilan baham:
1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish