Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu N noduri şi M arce, fiecare arc având o distanţă de valoare întreagă.

Cerință

Dându-se N, M şi cele M arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

Date de intrare

Fișierul de intrare graph.in conține pe prima linie numerele naturale N și M separate printr-un singur spațiu, iar pe următoarele M linii se află câte 3 numere A, B şi C, reprezentând un arc de la A către B de lungime C.

Date de ieșire

Fișierul de ieșire graph.out conține N linii cu câte N valori separate prin câte un spaţiu, reprezentând matricea drumurilor minime. Dacă nu există drum de la un nod a la un nod b, valoarea care trebuie afişată este x.

Restricții și precizări:

N <= 1500
M <= 30 000
Numerele nodurilor sunt valori cuprinse între 1 şi N
Lungimea arcelor aparţine intervalului [-1000; 1000]
Pentru 25% din teste N <= 150 şi M <= 1000
Pentru alte 40% din teste N <= 1000

Exemplu

graph.in

graph.out

0 7 6 5 x x 10 x 
x 0 -1 -2 x x 3 x 
x x 0 x x x x x 
x x x 0 x x x x 
x x x 2 0 6 1 x 
x x x x x 0 -5 x 
x x x x x x 0 x 
x -2 -3 -4 x 3 -2 0

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

#define TuTTy "Cosmin-Mihai Tutunaru"
#include<cstdio>
#include<cassert>
#include<vector>
#define infile "graph.in"
#define outfile "graph.out"
#define nMax 1513
#define inf (1<<29)

using namespace std;

vector < pair<int, int> > v[nMax];
int dp[nMax];

int sorted[nMax];
int hash[nMax];

int ap[nMax];
int n, m;

void read() {
    scanf("%d %d
", &n, &m);

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        assert(1 <= x && x <= n);
        assert(1 <= y && y <= n);

        v[x].push_back(make_pair(y, z));
        ap[y]++;
    }
}

int getNode() {

    for (int i = 1; i < n+1; ++i) {
        if (ap[i] == 0) {
            return i;
        }
    }

    assert(true == false);

    return -1;
}

void addNode(int x) {
    ap[x] = -1;

    for (unsigned i = 0; i < v[x].size(); ++i) {
        ap[v[x][i].first]--;
    }
}

void sort() {

    for (int i = 0; i < n; ++i) {
        int node = getNode();
        addNode(node);

        sorted[i] = node;
        hash[node] = i;
    }

}

void solve() {

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < n+1; ++j) {
            dp[j] = inf;
        }

        dp[i+1] = 0;

        for (int j = hash[i+1]; j < n; ++j) {
           int node = sorted[j];

           if (dp[node] == inf) {
               continue;
           }

           for (unsigned k = 0; k < v[node].size(); ++k) {
               assert(j < hash[v[node][k].first]);
               dp[v[node][k].first] = min(dp[v[node][k].first], dp[node] + v[node][k].second);
           }
        }

        for (int j = 1; j < n+1; ++j) {
            if (dp[j] == inf) {
                printf("x ");
            } else {
                printf("%d ", dp[j]);
            }
        }

        printf("
");

    }
}

int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    read();
    sort();
    solve();

    fclose(stdin);
    fclose(stdout);
    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 #146 graph

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

Rezolvare completă PbInfo #146 graph