Rezolvare completă PbInfo #3446 Ateleport

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 au Ti = 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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Ateleport:

/// student Alexandru Turdean  
/// Universitatea Tehnica din Cluj-Napoca

#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{ /// pentru usurinta se poate folosi priority_queue
    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]; /// timp_minim[x][y][z] = timpul minim pentru a ajunge in nodul x cu y teleportari si z muchii parcurse din teleportarea curenta
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; /// am ajuns intr-o stare in care am mai fost cu un timp mai mic

        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) /// incepem teleportare noua
            {
                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) /// continuam teleportarea
            {
                    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; /// folosim canalul de transport
            y.teleportari = x.teleportari;
            y.muchii_teleportarea_curenta = 0;
            update(y);
        }
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3446 Ateleport

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3446 Ateleport de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!