# PBinfo #146 – graph – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

8 9
1 2 7
2 3 -1
2 4 -2
2 7 3
8 2 -2
8 6 3
5 4 2
5 6 6
6 7 -5
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

## Cod sursă C++

```cpp
#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("\n");
    }
}
int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
    read();
    sort();
    solve();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/146)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/146/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-146/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)