Rezolvare completă PbInfo #1136 Dragoni

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:

  1. Să zboare de pe insula i pe o altă insulă x cu dragonul pe care îl are, folosind o rută directă j între insulele i si x, bineînțeles doar dacă Dj ≤ Dmaxt.
  2. Să schimbe dragonul din specia t pe care îl are cu un dragon din specia i aflat 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 ≤ 800
  • 1 ≤ M ≤ 6000
  • 1 ≤ Dmaxi ≤ 50 000, pentru orice 1 ≤ i ≤ N.
  • 1 ≤ Aj, Bj ≤ N, pentru orice 1 ≤ j ≤ M.
  • 1 ≤ Dj ≤ 50 000, pentru orice 1 ≤ 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 1 pe insula 2 o distanță de 5 cu dragonul din specia 1.
  • Zboară de pe insula 2 pe insula 3 o distanță de 6 cu dragonul din specia 1.
  • Schimbă dragonul din specia 1 cu dragonul aflat pe insula 3, care poate zbura o distanță maximă de 13.
  • Zboară de pe insula 3 pe insula 1 o distanță de 7 cu dragonul din specia 3.
  • Zboară de pe insula 1 pe insula 5 o distanță de 10 cu dragonul din specia 3.

În total el parcurge o distanță de 5 + 6 + 7 + 10 = 28.

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 Dragoni:

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define maxn 810
#define maxm 6010
#define inf (1LL*1000000000*1000000000)

int cer, n, m, a[maxm], b[maxm], d[maxm], dmax[maxn];
int f[maxn*maxn];
long long dist[maxn*maxn];
vector<int> v[maxn], w[maxn];
vector<pair<long long, int> > h;

int getNode(int lvl, int nod)
{
    return (lvl-1)*n+nod;
}

void dijkstra()
{
    for(int i=1; i<=n*n; ++i)
        dist[i]=inf;

    dist[1]=0;
    h.push_back(make_pair(0, 1));

    int nod;
    long long cdist;

    while(!h.empty())
    {
        nod=h[0].second;

        if(nod==n*n)
            break;

        cdist=-h[0].first;
        pop_heap(h.begin(), h.end());
        h.pop_back();

        if(f[nod])
            continue;

        f[nod]=1;
        int fiu, dragon = (nod-1)/n+1, node = (nod-1)%n+1;

        fiu = getNode(node, node);
        if(dist[fiu]>cdist)
        {
            dist[fiu]=cdist;
            h.push_back(make_pair(-dist[fiu], fiu));
            push_heap(h.begin(), h.end());
        }

        for(int i=0; i<v[node].size(); ++i)
        {
            fiu = getNode(dragon, v[node][i]);
            if(dist[fiu]>cdist+w[node][i] && w[node][i]<=dmax[dragon])
            {
                dist[fiu]=cdist+w[node][i];
                h.push_back(make_pair(-dist[fiu], fiu));
                push_heap(h.begin(), h.end());
            }
        }
    }
}

int cerinta1()
{
    int best=dmax[1];

    for(int i=2; i<=n; ++i)
        if(dist[i]!=inf && dmax[i]>best)
            best=dmax[i];

    return best;
}

int main()
{
    freopen("dragoni.in", "r", stdin);
    freopen("dragoni.out", "w", stdout);

    scanf("%d", &cer);
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i)
        scanf("%d", &dmax[i]);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d%d", &a[i], &b[i], &d[i]);
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
        w[a[i]].push_back(d[i]);
        w[b[i]].push_back(d[i]);
    }

    dijkstra();

    if(cer==1)
        printf("%d
", cerinta1());
    else
        printf("%lld
", dist[n*n]);

    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 #1136 Dragoni

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1136 Dragoni 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!