# PBinfo #4357 – Oxford – Rezolvare C++

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

## Enunț

Premierul Marii Britanii, Rishi Sunak, a decis să reorganizeze structura administrativă a comitatului Oxfordshire. În Oxfordshire sunt prezente N orașe numerotate de la 1 la N, conectate prin M autostrăzi (drumuri unidirecționale ce conectează două orașe). Rishi a hotărât ca toate orașele cu proprietatea că cetățenii tuturor celorlalte orașe pot ajunge în ele prin intermediul autostrăzilor să devină reședințe. Deoarece numărul de orașe și autostrăzi din Oxfordshire este foarte mare, Rishi vă cere ajutorul în rezolvarea a două probleme cheie.

Cerința
1. Care sunt indicii orașelor reședință din Oxfordshire.
2. Care este distanța minimă de la fiecare oraș până la cea mai apropiată reședință de acel oraș.

Date de intrare
Intrarea standard conține pe prima linie trei numere C, N și M, separate printr-un spațiu, unde C reprezintă numărul cerinței, N numărul de orașe și M numărul de autostrăzi. Pe următoarele M linii se află câte trei numere i, j și d, separate prin spații, reprezentând descrierea autostrăzilor: există o autostradă de la orașul cu indicele i până la orașul cu indicele j cu lungimea d.

Date de ieșire
Ieșirea standard va conține o singură linie. Dacă C = 1, se vor afișa indicii reședințelor, ordonați crescător, separați prin spații. Dacă C = 2, se vor afișa N numere, separate prin spații, reprezentând distanțele minime de la fiecare oraș (cu indici de la 1 la N) până la cea mai apropiată reședință de orașul respectiv (dacă orașul este reședință se va afișa 0).

Restricții și precizări

2 ≤ N ≤ 100.000
• 1 ≤ M ≤ min(N ∗ (N − 1), 200.000)
• 1 ≤ d ≤ 10.000
• nu există o autostradă care să conecteze un oraș cu el însuși
• nu există mai multe autostrăzi care să conecteze aceleași două orașe în același sens
• în toate testele există cel puțin o reședință

Exemplul 1:
Intrare

1 6 6
4 3 2
2 4 4
4 2 2
5 4 6
6 2 7
1 3 10
Ieșire

3
Explicație
Orașul cu indicele 3 este singura reședință deoarece este singurul oraș în care se poate ajunge din toate celelalte orașe (vezi Figura 1).

Exemplul 2:
Intrare

2 9 12
8 4 30
4 6 16
6 1 13
6 5 1
5 2 26
7 2 10
3 9 23
9 3 5
1 4 7
4 5 18
2 5 8
9 2 19
Ieșire

24 0 42 17 0 1 10 47 19
Explicație
Sunt două reședințe: orașele cu indicii 2 și 5. Orașele cu indicii 1, 4, 6 și 8 sunt mai aproape de reședința cu indicele 5. Orașele cu indicii 3, 7 și 9 sunt mai aproape de reședința cu indicele 2. (vezi Figura 2).

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
class Kosaraju {
    vector<bool> plus, minus;
    stack<int> st;
    vector<vector<int>> ctc;
    void dfs_plus(int nod, vector<vector<int>> &G) {
        plus[nod] = 1;
        for (auto it : G[nod])
            if (!plus[it])
                dfs_plus(it, G);
        st.push(nod);
    }
    void dfs_minus(int nod, vector<vector<int>> &GT) {
        ctc.back().push_back(nod);
        minus[nod] = 1;
        for (auto it : GT[nod])
            if (!minus[it])
                dfs_minus(it, GT);
    }
public:
    vector<vector<int>> solve(int N, vector<vector<int>> &G, vector<vector<int>> &GT) {
        plus.resize(N + 1);
        minus.resize(N + 1);
        for (int i = 1; i <= N; ++i)
            if (!plus[i])
                dfs_plus(i, G);
        while (!st.empty()) {
            int nod = st.top();
            st.pop();
            if (!minus[nod]) {
                ctc.push_back({});
                dfs_minus(nod, GT);
            }
        }
        return ctc;
    }
};
vector<int> Dijkstra(int N, vector<vector<pair<int, int>>> &G, int nod) {
    priority_queue<pair<int, int>,vector<pair<int, int>>,greater<pair<int, int>>> Q;
    vector<int> dist(N + 1, INT_MAX);
    dist[nod] = 0;
    Q.push({0,nod});
    while (!Q.empty()){
        int nod = Q.top().second, cost = Q.top().first;
        Q.pop();
        if (dist[nod] != cost)
            continue;
        for (auto it : G[nod])
            if (cost + it.second < dist[it.first]){
                dist[it.first] = cost + it.second;
                Q.push({dist[it.first], it.first});
            }
    }
    return dist;
}
int main() {
    int C, N, M;
    cin >> C >> N >> M;
    vector<vector<int>> G(N + 1), GT(N + 1);
    vector<vector<pair<int, int>>> GM(N + 1);
    while (M--) {
        int i, j, d;
        cin >> i >> j >> d;
        G[i].push_back(j);
        GT[j].push_back(i);
        GM[j].push_back({i, d});
    }
    // prima cerinta
    vector<vector<int>> ctc = Kosaraju().solve(N, G, GT);
    vector<int> res = ctc.back();
    sort(res.begin(), res.end());
    if (C == 1) {
        for (auto it : res)
            cout << it << " ";
        cout << "\n";
    }
    else {
        // a doua cerinta
        vector<bool> is_res(N + 1);
        for (auto it : res)
            is_res[it] = 1;
        // graful modificat = graful transpus, dar toate resedintele devin nodul 0
        for (int i = 1; i <= N; ++i)
            if (is_res[i]) {
                for (auto it : GM[i]) 
                    if (!is_res[it.first])
                        GM[0].push_back(it);
            }
        vector<int> dist = Dijkstra(N, GM, 0);
        for (int i = 1; i <= N; ++i) {
            if (is_res[i])
                cout << "0 ";
            else cout << dist[i] << " ";
        }
    }
}
```

## Resurse

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