Um fazendeiro deseja transportar leite para T cidades (1 ≤ T ≤ 25.000), numeradas de 1 a T. As cidades são conectadas por R estradas (1 ≤ R ≤ 50.000) e P rotas aéreas (1 ≤ P ≤ 50.000). Cada estrada ou rota i liga a cidade Ai a Bi com custo Ci. Para estradas, 0 ≤ Ci ≤ 10.000; para rotas aéreas, -10.000 ≤ Ci ≤ 10.000. Estradas são bidirecionais, rotas aéreas são unidirecionais. Garante-se que não é possível voltar de Bi para Ai usando uma combinação de estradas e rotas aéreas. O objetivo é encontrar o menor custo para chegar a cada cidade a partir da cidade de partida S, ou informar que é impossível.

Entrada

Linha 1: quatro inteiros T, R, P, S.
Linhas 2 a R+1: três inteiros Ai, Bi, Ci (estrada).
Linhas R+2 a R+P+1: três inteiros Ai, Bi, Ci (rota aérea).

Saída

Para cada cidade i (1 a T), imprimir o custo mínimo a partir de S ou "NO PATH" se enatingível.

Exemplo

<strong>Entrada:</strong>
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

<strong>Saída:</strong>
NO PATH
NO PATH
5
0
-95
-100

Explicação: Partindo da cidade 4, pela estrada chega-se a 3 (custo 5). Depois, pelas rotas aéreas 3→5 (custo -100) e 4→6 (custo -100) obtêm-se os custos -95 e -100. As cidades 1 e 2 são inatingíveis.

Solução Algorítmica

Devido à presença de arestas negativas (rotas aéreas) e à garantia de que não existem ciclos negativos acessíveis a partir de S (a condição de não retorno garante que as rotas aéreas não formam ciclos com estradas), o problema pode ser resolvido com a seguinte abordagem:

1. Construir grafo com todas as arestas (estradas bidirecionais, rotas unidirecionais).
2. Identificar componentes fotremente conexas (CFCs) usando apenas as estradas (grafo não direcionado). Como as estradas são bidirecionais, cada CFC representa uma região onde é possível transitar livremente por estradas.
3. Para cada CFC, executar o algoritmo de Dijkstra internamente, pois dentro de uma CFC todas as arestas têm peso não negativo (estradas) ou, se houver rotas aéreas saindo de dentro, elas serão tratadas posteriormente.
4. Tratar as rotas aéreas como arestas dirigidas entre CFCs. Como não há ciclos entre CFCs (garantia do problema), podemos ordanar as CFCs topologicamente e processá-las em ordem.
5. Manter uma fila de CFCs com grau de entrada zero (topologia) e processar cada uma com Dijkstra, propagando distâncias para as CFCs vizinhas.

Abaixo, uma implementação em C++ que segue essa estratégia.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25005;
const int MAXM = 150005;
const int INF = 0x3f3f3f3f;

int numCidades, numEstradas, numRotas, origem;
int head[MAXN], to[MAXM], weight[MAXM], nxt[MAXM], edgeCnt = 0;

void addEdge(int a, int b, int c) {
    to[edgeCnt] = b;
    weight[edgeCnt] = c;
    nxt[edgeCnt] = head[a];
    head[a] = edgeCnt++;
}

int compId[MAXN], numComps = 0;
vector<int> compNodes[MAXN];
bool visited[MAXN];

void dfs(int u) {
    compId[u] = numComps;
    compNodes[numComps].push_back(u);
    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (!compId[v]) dfs(v);
    }
}

int dist[MAXN];
int indeg[MAXN];
queue<int> topoQueue;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
bool done[MAXN];

void dijkstra(int comp) {
    // Initialize priority queue with all nodes of this component
    for (int node : compNodes[comp]) {
        pq.push({dist[node], node});
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (done[u]) continue;
        done[u] = true;
        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (done[v]) continue;
            int nd = d + weight[i];
            if (nd < dist[v]) {
                dist[v] = nd;
                if (compId[u] == compId[v]) {
                    pq.push({nd, v});
                }
            }
            // If edge goes to another component, reduce indegree
            if (compId[u] != compId[v]) {
                int vid = compId[v];
                if (--indeg[vid] == 0) {
                    topoQueue.push(vid);
                }
            }
        }
    }
}

void topologicalSort() {
    for (int i = 1; i <= numComps; ++i) {
        if (indeg[i] == 0) topoQueue.push(i);
    }
    while (!topoQueue.empty()) {
        int comp = topoQueue.front(); topoQueue.pop();
        dijkstra(comp);
    }
}

int main() {
    memset(head, -1, sizeof head);
    memset(dist, 0x3f, sizeof dist);
    scanf("%d%d%d%d", &numCidades, &numEstradas, &numRotas, &origem);
    dist[origem] = 0;

    int a, b, c;
    // Estradas (bidirecionais)
    for (int i = 0; i < numEstradas; ++i) {
        scanf("%d%d%d", &a, &b, &c);
        addEdge(a, b, c);
        addEdge(b, a, c);
    }

    // Identificar componentes apenas com estradas (bidirecionais)
    for (int i = 1; i <= numCidades; ++i) {
        if (!compId[i]) {
            ++numComps;
            dfs(i);
        }
    }

    // Rotas aéreas (apenas uma direção)
    for (int i = 0; i < numRotas; ++i) {
        scanf("%d%d%d", &a, &b, &c);
        addEdge(a, b, c);
        indeg[compId[b]]++;  // incrementa grau de entrada do componente destino
    }

    topologicalSort();

    for (int i = 1; i <= numCidades; ++i) {
        if (dist[i] > INF/2) printf("NO PATH\n");
        else printf("%d\n", dist[i]);
    }

    return 0;
}