No problema POJ 3268, existe um ponto de encontro designado como x onde ocorre uma reunião. Todos os outros pontos no grafo precisam viajar até x e, em seguida, retornar ao ponto de partida original. O objetivo é calcular a distância total máxima percorrida em um ciclo completo de ida e volta.

Para resolver isso, precisamos encontrar os caminhos mais curtos de cada nó para x e de x para cadda nó. Devido à natureza direcionada do grafo, algoritmos de caminho mínimo como Dijkstra e SPFA são adequados.

Abordagem com Algoritmo de Dijkstra

Esta solução executa o algoritmo de Dijkstra duas vezes: uma para calcular as distâncias mínimas de todos os nós até x (caminhos inversos) e outra para as distâncias mínimas de x até todos os nós (caminhos diretos). A implemetnação abaixo utiliza uma matriz de adjacência para representar o grafo.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>

using namespace std;

const int MAXIMO_NOS = 1010;
const int SEM_CAMINHO = INT_MAX;

int matrizAdj[MAXIMO_NOS][MAXIMO_NOS];
int totalNos, totalArestas, pontoCentral;
int distParaX[MAXIMO_NOS], distDeX[MAXIMO_NOS];
bool processado[MAXIMO_NOS];

void prepararMatriz() {
    for (int i = 1; i <= totalNos; ++i) {
        for (int j = 1; j <= totalNos; ++j) {
            if (i == j) {
                matrizAdj[i][j] = 0;
            } else {
                matrizAdj[i][j] = SEM_CAMINHO;
            }
        }
    }
}

void dijkstraParaX() {
    for (int i = 1; i <= totalNos; ++i) {
        distParaX[i] = matrizAdj[i][pontoCentral];
    }
    memset(processado, false, sizeof(processado));
    processado[pontoCentral] = true;

    for (int iteracao = 0; iteracao < totalNos; ++iteracao) {
        int menor = SEM_CAMINHO;
        int noSelecionado = -1;
        for (int no = 1; no <= totalNos; ++no) {
            if (!processado[no] && distParaX[no] < menor) {
                menor = distParaX[no];
                noSelecionado = no;
            }
        }
        if (noSelecionado == -1) break;
        processado[noSelecionado] = true;
        for (int vizinho = 1; vizinho <= totalNos; ++vizinho) {
            if (!processado[vizinho] && distParaX[vizinho] > matrizAdj[vizinho][noSelecionado] + distParaX[noSelecionado]) {
                distParaX[vizinho] = matrizAdj[vizinho][noSelecionado] + distParaX[noSelecionado];
            }
        }
    }
}

void dijkstraDeX() {
    for (int i = 1; i <= totalNos; ++i) {
        distDeX[i] = matrizAdj[pontoCentral][i];
    }
    memset(processado, false, sizeof(processado));
    processado[pontoCentral] = true;

    for (int iteracao = 0; iteracao < totalNos; ++iteracao) {
        int menor = SEM_CAMINHO;
        int noSelecionado = -1;
        for (int no = 1; no <= totalNos; ++no) {
            if (!processado[no] && distDeX[no] < menor) {
                menor = distDeX[no];
                noSelecionado = no;
            }
        }
        if (noSelecionado == -1) break;
        processado[noSelecionado] = true;
        for (int vizinho = 1; vizinho <= totalNos; ++vizinho) {
            if (!processado[vizinho] && distDeX[vizinho] > distDeX[noSelecionado] + matrizAdj[noSelecionado][vizinho]) {
                distDeX[vizinho] = distDeX[noSelecionado] + matrizAdj[noSelecionado][vizinho];
            }
        }
    }
}

int main() {
    while (scanf("%d %d %d", &totalNos, &totalArestas, &pontoCentral) == 3) {
        prepararMatriz();
        int origem, destino, custo;
        for (int i = 0; i < totalArestas; ++i) {
            scanf("%d %d %d", &origem, &destino, &custo);
            if (custo < matrizAdj[origem][destino]) {
                matrizAdj[origem][destino] = custo;
            }
        }
        dijkstraParaX();
        dijkstraDeX();

        int maxDistanciaTotal = -1;
        for (int i = 1; i <= totalNos; ++i) {
            if (distParaX[i] != SEM_CAMINHO && distDeX[i] != SEM_CAMINHO) {
                int distanciaCiclo = distParaX[i] + distDeX[i];
                if (distanciaCiclo > maxDistanciaTotal) {
                    maxDistanciaTotal = distanciaCiclo;
                }
            }
        }
        printf("%d\n", maxDistanciaTotal);
    }
    return 0;
}

Abordagem com Algoritmo SPFA e Grafo Invertido

Uma alternativa eficiente é usar o algoritmo SPFA. Para obter as distâncias de volta, construímos um grafo invertido revertando as direções das arestas. Assim, executamos o SPFA no grafo original para distâncias de ida e no grafo invertido para distâncias de volta. Esta implementação emprega listas de adjacência para melhor desempenho.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <vector>

using namespace std;

const int LIMITE_NOS = 101000;
const int INFINITO = INT_MAX;

int qtdNos, qtdArestas, noEncontro;
vector<pair<int, int>> rede[LIMITE_NOS];
vector<pair<int, int>> redeInvertida[LIMITE_NOS];
int distIda[LIMITE_NOS], distVolta[LIMITE_NOS];
bool naFila[LIMITE_NOS];

void spfaCalcularIda() {
    for (int i = 1; i <= qtdNos; ++i) {
        distIda[i] = INFINITO;
    }
    distIda[noEncontro] = 0;
    memset(naFila, false, sizeof(naFila));
    queue<int> fila;
    fila.push(noEncontro);
    naFila[noEncontro] = true;

    while (!fila.empty()) {
        int noCorrente = fila.front();
        fila.pop();
        naFila[noCorrente] = false;
        for (const auto& aresta : rede[noCorrente]) {
            int vizinho = aresta.first;
            int peso = aresta.second;
            if (distIda[vizinho] > distIda[noCorrente] + peso) {
                distIda[vizinho] = distIda[noCorrente] + peso;
                if (!naFila[vizinho]) {
                    naFila[vizinho] = true;
                    fila.push(vizinho);
                }
            }
        }
    }
}

void spfaCalcularVolta() {
    for (int i = 1; i <= qtdNos; ++i) {
        distVolta[i] = INFINITO;
    }
    distVolta[noEncontro] = 0;
    memset(naFila, false, sizeof(naFila));
    queue<int> fila;
    fila.push(noEncontro);
    naFila[noEncontro] = true;

    while (!fila.empty()) {
        int noCorrente = fila.front();
        fila.pop();
        naFila[noCorrente] = false;
        for (const auto& aresta : redeInvertida[noCorrente]) {
            int vizinho = aresta.first;
            int peso = aresta.second;
            if (distVolta[vizinho] > distVolta[noCorrente] + peso) {
                distVolta[vizinho] = distVolta[noCorrente] + peso;
                if (!naFila[vizinho]) {
                    naFila[vizinho] = true;
                    fila.push(vizinho);
                }
            }
        }
    }
}

int main() {
    int u, v, w;
    while (scanf("%d %d %d", &qtdNos, &qtdArestas, &noEncontro) == 3) {
        for (int i = 1; i <= qtdNos; ++i) {
            rede[i].clear();
            redeInvertida[i].clear();
        }
        for (int i = 0; i < qtdArestas; ++i) {
            scanf("%d %d %d", &u, &v, &w);
            rede[u].emplace_back(v, w);
            redeInvertida[v].emplace_back(u, w);
        }
        spfaCalcularIda();
        spfaCalcularVolta();

        int maxDistancia = -1;
        for (int i = 1; i <= qtdNos; ++i) {
            if (distIda[i] != INFINITO && distVolta[i] != INFINITO) {
                int totalDistancia = distIda[i] + distVolta[i];
                if (totalDistancia > maxDistancia) {
                    maxDistancia = totalDistancia;
                }
            }
        }
        printf("%d\n", maxDistancia);
    }
    return 0;
}