Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există N planete diferite și M canale bidirecţionale de transport de tipul (x, y, t) care îţi permit să te deplasezi de pe planeta x pe planeta y (sau invers) în t secunde.
Dar Marian este un adevărat inginer și, pentru că i se pare foarte ineficientă această metodă de transport, a dezvoltat un dispozitiv care îți permite teleportarea de pe o planetă x pe orice altă planetă y în P secunde cu condiţia că ai putea ajunge pornind de pe planeta x pe planeta y folosind maxim L canale de transport.
Acest dispozitiv este momentan doar un prototip, așa că nu îl poate folosi mai mult de K ori. Marian se află pe planeta 1 și te roagă să îi spui care e timpul minim necesar pentru a ajunge pe planeta N.
Cerința
Să se scrie un program care calculează timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.
Date de intrare
Fișierul de intrare ateleport.in conține pe prima linie 5 valori N, M, P, L, K, separate printr-un singur spaţiu, cu semnificaţia din enunţ.
Pe fiecare din următoarele M linii se vor afla câte 3 valori Xi, Yi, Ti care descriu un canal de transport.
Date de ieșire
Fișierul de ieșire ateleport.out va conține o singură valoare pe prima linie care reprezintă
Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există N planete diferite și M canale bidirecţionale de transport de tipul (x, y, t) care îţi permit să te deplasezi de pe planeta x pe planeta y (sau invers) în t secunde.
Dar Marian este un adevărat inginer și, pentru că i se pare foarte ineficientă această metodă de transport, a dezvoltat un dispozitiv care îți permite teleportarea de pe o planetă x pe orice altă planetă y în P secunde cu condiţia că ai putea ajunge pornind de pe planeta x pe planeta y folosind maxim L canale de transport.
Acest dispozitiv este momentan doar un prototip, așa că nu îl poate folosi mai mult de K ori. Marian se află pe planeta 1 și te roagă să îi spui care e timpul minim necesar pentru a ajunge pe planeta N.
Cerința
Să se scrie un program care calculează timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.
Date de intrare
Fișierul de intrare ateleport.in conține pe prima linie 5 valori N, M, P, L, K, separate printr-un singur spaţiu, cu semnificaţia din enunţ.
Pe fiecare din următoarele M linii se vor afla câte 3 valori Xi, Yi, Ti care descriu un canal de transport.
Date de ieșire
Fișierul de ieșire ateleport.out va conține o singură valoare pe prima linie care reprezintă
timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.
Restricții și precizări
1 < N, M ≤ 10 000;0 ≤ L, K ≤ 10;1 < Ti, P ≤ 100 000;1 < Xi, Yi≤ N;- între oricare două planete există cel mult un canal;
- pentru teste în valoare de 30 de puncte se garantează că
K = 0și toate canalele de comunicare auTi= 1; - pentru ALTE teste în valoare de 20 de puncte se garantează că
K = 0; - pentru ALTE teste în valoare de 20 de puncte se garantează că
N ≤ 300; - se garantează că pentru toate testele există soluţie;
- în concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.
Exemplul 1
ateleport.in
6 7 3 2 1 1 2 2 1 3 5 2 3 4 2 4 23 3 4 6 5 4 7 5 6 9
ateleport.out
14
Explicație
Dispozitivul se poate folosi cel mult o dată. Pentru a ajunge pe planeta 6 în timp minim vom parcurge canalul 1 → 2 apoi ne vom teleporta până pe planeta 5 de unde vom mai parcurge canalul 5 → 6. Costul final este 2 + 3(teleportare) + 9 = 14.
Exemplul 1
ateleport.in
6 7 3 2 0 1 2 2 1 3 5 2 3 4 2 4 23 3 4 6 5 4 7 5 6 9
ateleport.out
27
Explicație
Dispozitivul nu se poate folosi deloc. Pentru a ajunge pe planeta 6 de pe planeta 1 în timp minim, se vor parcurge canalele în ordinea 1→3→4→5→6 și se obține timpul 5+6+7+9=27 de secunde.
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("ateleport.in");
ofstream fout("ateleport.out");
struct muchie{
int nod;
int timp;
};
struct element{
int nod;
int timp;
int muchii_teleportarea_curenta;
int teleportari;
bool operator<(const element &x) const
{
return timp < x.timp;
}
};
struct min_heap{
element v[1000001];
int size = 0;
element top()
{
return v[1];
}
void push(element el)
{
size++;
v[size] = el;
int pos = size;
while(pos != 1)
if(v[pos] < v[pos/2])
swap(v[pos/2],v[pos]), pos/=2;
else
break;
}
void pop()
{
if(size == 0)
return;
swap(v[1],v[size]);
size--;
int pos = 1;
while(pos*2+1 <= size)
{
if(v[pos*2] < v[pos] && v[pos*2] < v[pos*2+1])
swap(v[pos*2], v[pos]), pos = pos*2;
else if(v[pos*2+1] < v[pos])
swap(v[pos*2+1], v[pos]), pos = pos*2+1;
else
break;
}
if(pos*2 == size && v[pos*2] < v[pos])
swap(v[pos*2], v[pos]);
}
};
int n,m,p,l,k;
int timp_minim[10001][11][11];
vector<muchie> muchii[10001];
min_heap myHeap;
void update(element &y)
{
if(y.timp < timp_minim[y.nod][y.teleportari][y.muchii_teleportarea_curenta])
{
timp_minim[y.nod][y.teleportari][y.muchii_teleportarea_curenta] = y.timp;
myHeap.push(y);
}
}
int main()
{
fin >> n >> m >> p >> l >> k;
for(int i = 1; i <= m; i++)
{
int x,y,t;
fin >> x >> y >> t;
muchii[x].push_back(muchie{y,t});
muchii[y].push_back(muchie{x,t});
}
for(int x = 0; x <= n; x++)
for(int y = 0; y <= 10; y++)
for(int z = 0; z <= 10; z++)
timp_minim[x][y][z] = 2000000000;
myHeap.push(element{1,0,0,0});
timp_minim[1][0][0] = 0;
while(myHeap.size > 0)
{
element x;
x = myHeap.top();
myHeap.pop();
if(timp_minim[x.nod][x.teleportari][x.muchii_teleportarea_curenta] < x.timp)
continue;
if(x.nod == n)
{
fout << x.timp;
return 0;
}
for(int i = 0; i < muchii[x.nod].size(); i++)
{
element y;
y.nod = muchii[x.nod][i].nod;
if(x.teleportari < k)
{
y.timp = x.timp + p;
y.muchii_teleportarea_curenta = 1;
y.teleportari = x.teleportari + 1;
update(y);
}
if(x.muchii_teleportarea_curenta > 0 && x.muchii_teleportarea_curenta < l)
{
y.timp = x.timp;
y.muchii_teleportarea_curenta = x.muchii_teleportarea_curenta + 1;
y.teleportari = x.teleportari;
update(y);
}
y.timp = x.timp + muchii[x.nod][i].timp;
y.teleportari = x.teleportari;
y.muchii_teleportarea_curenta = 0;
update(y);
}
}
return 0;
}
