Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:
Într-o lume în care vikingii pot zbura cu dragonii există N insule. Hiccup, șeful tribului de vikingi aflat pe insula 1, știe M rute directe de zbor bidirecționale între insule. Pentru fiecare j intre 1 si M, ruta j unește insulele Aj și Bj și are lungime Dj.
Pe fiecare insulă i, (1 ≤ i ≤ n) există dragoni din specia i care pot zbura fără a se opri pentru odihnă o distanță maximă Dmaxi. Cu alte cuvinte, dragonii de pe insula i vor putea parcurge orice rută j, (1 ≤ j ≤ m) pentru care Dj ≤ Dmaxi, indiferent de ce alte drumuri au făcut anterior.
Hiccup dorește să ajungă de pe insula 1 pe insula N pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia 1 (de pe insula 1). Apoi, dacă la un moment dat Hiccup se află pe o insula i, (1 ≤ i ≤ n) având cu el un dragon din specia t, el poate:
- Să zboare de pe insula
ipe o altă insulăxcu dragonul pe care îl are, folosind o rută directăjîntre insuleleisix, bineînțeles doar dacăDj≤ Dmaxt. - Să schimbe dragonul din specia
tpe care îl are cu un dragon din speciaiaflat pe insula respectivă.
Cerințe
a. Să se determine distanța maxima Dmaxi caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:
Într-o lume în care vikingii pot zbura cu dragonii există N insule. Hiccup, șeful tribului de vikingi aflat pe insula 1, știe M rute directe de zbor bidirecționale între insule. Pentru fiecare j intre 1 si M, ruta j unește insulele Aj și Bj și are lungime Dj.
Pe fiecare insulă i, (1 ≤ i ≤ n) există dragoni din specia i care pot zbura fără a se opri pentru odihnă o distanță maximă Dmaxi. Cu alte cuvinte, dragonii de pe insula i vor putea parcurge orice rută j, (1 ≤ j ≤ m) pentru care Dj ≤ Dmaxi, indiferent de ce alte drumuri au făcut anterior.
Hiccup dorește să ajungă de pe insula 1 pe insula N pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia 1 (de pe insula 1). Apoi, dacă la un moment dat Hiccup se află pe o insula i, (1 ≤ i ≤ n) având cu el un dragon din specia t, el poate:
- Să zboare de pe insula
ipe o altă insulăxcu dragonul pe care îl are, folosind o rută directăjîntre insuleleisix, bineînțeles doar dacăDj≤ Dmaxt. - Să schimbe dragonul din specia
tpe care îl are cu un dragon din speciaiaflat pe insula respectivă.
Cerințe
a. Să se determine distanța maxima Dmaxi caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.
Date de intrare
Fișierul de intrare dragoni.in conține pe prima linie numărul p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se găsesc două numere naturale N și M reprezentând numărul de insule, respectiv numărul de rute directe între insule. Pe a treia linie se găsesc N numere naturale, al i-lea dintre acestea reprezentând distanta maximă Dmaxi pe care o poate zbura un dragon de pe insula i. Pe următoarele M linii sunt descrise cele M rute directe. Pe fiecare dintre aceste linii se găsesc câte trei numere naturale A, B și D cu semnificația că există rută bidirecțională de lungime D între insulele A și B.
Date de ieșire
n fișierul de ieșire dragoni.out se va afișa un singur număr natural.
Dacă valoarea lui p este 1, se rezolvă numai cerința a.
În acest caz numărul afișat va reprezenta distanța maximă Dmaxi a unui dragon i la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
Daca valoarea lui p este 2, se va rezolva numai cerința b,
În acest caz numărul afișat va reprezenta distanța minima pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.
Restricții și precizări
1 ≤ N ≤ 8001 ≤ M ≤ 60001 ≤ Dmaxi≤ 50 000, pentru orice1 ≤ i ≤ N.1 ≤ Aj, Bj≤ N, pentru orice1 ≤ j ≤ M.1 ≤ Dj≤ 50 000, pentru orice1 ≤ j ≤ M.- Se garantează că Hiccup poate ajunge pe insula
N. - Se garantează că răspunsul oricărei cerințe este un număr natural mai mic decât
109. - Pentru rezolvarea corectă a primei cerințe se acordă 20% din punctajul testului respectiv.
- Pentru rezolvarea corectă a celei de-a doua cerințe se acordă 80% din punctajul testului respectiv.
Exemplul 1
dragoni.in
1 5 6 6 3 13 20 26 1 2 5 1 3 7 1 5 10 2 3 6 3 4 5 3 5 14
dragoni.out
20
Explicație
p = 1 deci se va rezolva cerința a).
Există N = 5 insule si M = 6 rute între ele. Hiccup pornește de pe insula 1 având un dragon care poate zbura o distanță de maxim 6. Cu acest dragon poate ajunge doar pe insulele 1, 2, 3 si 4, întrucât pentru a ajunge pe insula 5 el ar fi obligat sa parcurgă o ruta de lungime mai mare decât 6.
Distanta maxima pe care o poate zbura un dragon aflat pe insulele 1, 2, 3 sau 4 este deci 20 (dragonul de pe insula 4). Se observă că dragonul care poate zbura o distanță de 26 se afla pe insula 5 și este inaccesibil.
Exemplul 1
dragoni.in
2 5 6 6 3 13 20 26 1 2 5 1 3 7 1 5 10 2 3 6 3 4 5 3 5 14
dragoni.out
28
Explicație
p = 2 deci se va rezolva cerința a).
Există N = 5 insule și M = 6 rute între ele. Pentru a parcurge o distanță minimă de 28 între insulele 1 și N, Hiccup face următorii pași:
- Zboară de pe insula
1pe insula2o distanță de5cu dragonul din specia1. - Zboară de pe insula
2pe insula3o distanță de6cu dragonul din specia1. - Schimbă dragonul din specia
1cu dragonul aflat pe insula3, care poate zbura o distanță maximă de13. - Zboară de pe insula
3pe insula1o distanță de7cu dragonul din specia3. - Zboară de pe insula
1pe insula5o distanță de10cu dragonul din specia3.
În total el parcurge o distanță de 5 + 6 + 7 + 10 = 28.
#include <bits/stdc++.h>
using namespace std;
#define Inf 0x3f3f3f3f
ifstream cin("dragoni.in");
ofstream cout("dragoni.out");
using PI = pair<int , int>;
int cer , n , m , x , y , w , dr[1001] , v[1001] , s , D[1001][1001] , d[10001];
vector <pair<int , int>> G[801];
void dfs(int nod , int dist , int &s)
{
v[nod] = 1;
for(auto x : G[nod])
if(!v[x.first] && x.second <= dist)
{
v[x.first] = 1;
if(dr[x.first] > s)
s = dr[x.first];
dfs(x.first , dist , s);
}
}
void dijkstra(int s)
{
priority_queue <PI , vector<PI> , greater<PI>> Q;
D[s][s] = 0;
Q.push({0 , s});
while(!Q.empty())
{
x = Q.top().second;
y = Q.top().first;
Q.pop();
if(y > D[s][x]) continue;
for(auto& i:G[x])
{
int nodnou = i.first;
int costnou = i.second;
if(dr[s] >= costnou && D[s][nodnou] > y + costnou)
{
D[s][nodnou] = y + costnou;
Q.push({D[s][nodnou] , nodnou});
}
}
}
}
int main()
{
cin >> cer >> n >> m;
for(int i = 1 ; i <= n ; ++i)
cin >> dr[i];
for(int i = 1 ; i <= m ; ++i)
{
cin >> x >> y >> w;
G[x].push_back({y , w});
G[y].push_back({x , w});
}
if(cer == 1)
{
dfs(1 , dr[1] , s);
cout << s;
}
else
{
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
D[i][j] = Inf;
for(int i = 1 ; i <= n ; i++)
dijkstra(i) , d[i] = D[1][i];
/*for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= n ; j++)
cout << D[i][j] << " ";
cout << 'n';
}*/
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= n ; j++)
if(d[i] > d[j] + D[j][i])
d[i] = d[j] + D[j][i];
}
cout << d[n];
}
}
