Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Traseu

Adăugată de :
sorynsoo
Sursă :
XOR2010
Autor :
-
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
200 ms
Limită memorie :
16384 kbytes

Ovi tocmai şi-a cumpărat maşină şi doreşte să facă o călătorie într-un alt oraş. Pentru că este şofer începător, el îşi planifică să mergă spre oraşul de destinaţie în mai multe zile trecând zilnic prin câte un oraş intermediar. Astfel, în fiecare zi va parcurge drumul direct de la un oraş X la un oraş Y, în Y se va odihni, urmând ca următoarea zi să parcurgă o nouă etapă din traseu în acelaşi mod. Ovi s-a uitat pe hartă, unde identifică N oraşe numerotate de la 1 la N şi află astfel între ce oraşe sunt şosele (bidirecţionale) şi care este lungimea acestor şosele. Nu-l interesează să ajungă la destinaţie parcurgând un traseu de lungime minimă, nici în cât mai puţine zile, ci ca distanţa maximă parcursă zilnic să fie cât mai mică. Deci dacă traseul îl parcurge în k zile, iar distanţele parcurse zilnic sunt d1, d2, ..., dk, notând cu dmax valoarea maximă din acest şir, Ovi doreşte ca valoarea dmax să fie cât mai mică posibil.

 

Cerinţa

Scrieţi un program prin care să-l ajutaţi pe Ovi ca plecând din oraşul natal să ajungă în oraşul de destinaţie în una sau mai multe etape, iar distanţa dmax să fie minimă.

 

Date de intrare

Fişierul de intrare conţine pe prima linie numărul natural N reprezentând numărul de oraşe. Pe linia a doua se află numărul natural M reprezentând numărul de şosele bidirecţionale de pe hartă. Pe următoarele M linii se află câte 3 numere naturale separate prin spaţiu X, Y, D cu semnificaţia: există şosea bidirecţională între oraşele X şi Y de lungime D (X şi Y sunt oraşe diferite). Pe ultima linie se găsesc două numere naturale S şi F, unde S este oraşul de plecare, iar F este oraşul destinaţie.

 

Date de iesire

Fişierul de iesire va conţine o singură linie pe care va fi scris un singur număr reprezentând distanţa dmax dintre două oraşe de pe traseu, minimă posibil.

 

Restricţii şi precizări:

  • 2 <= N <= 500
  • 2 <= M <= 50 000
  • Distanţele dintre oraşe sunt numere naturale cuprinse între 1 şi 10 000
  • Va exista întotdeauna cel puţin un traseu de la oraşul de plecare la destinaţie

 

Exemple

  Date de intrare

  Date de iesire

  Explicaţie

  7

  9

  1 2 30

  1 3 20

  1 7 100

  2 4 70

  3 5 50

  5 4 10

  7 5 60

  6 5 40

  7 6 40

  1 7

50

  Traseul optim de la oraşul 1 la 7 care îndeplineşte cerinţele este 1-3-5-6-7, deoarece distanţa maximă dmax pe care este nevoit să o parcurgă într-o zi este 50 (între oraşele 3 şi 5).

  Mai există şi alte trasee care nu sunt optime, de exemplu:

  1-7 : distanţa dmax este 100

  1-2-4-5-7 : distanţa dmax este 70

  1-3-5-7 : distanţa dmax este 60

 

 


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Grafuri


Comentarii

Adauga un comentariu: Click !