viagem_de_succa.cpp

//
//  viagem_de_succa.cpp
//
//  Created by Lucca Siaudzionis on 06/05/15.
//
//  Viagem de Succa - Noic

#include <cstdio>
#include <algorithm> // para usar a função min(a, b)
using namespace std;

//---------------------
#define MAXN 1010
// como não existe o Infinito no computador, usaremos um número bem grande
#define INFINITO 999999999

int n, m;                // número de vértices e arestas
int cidade_noic;         // cidade onde está o Noic
int cidade_succa;        // cidade onde está o Succa
int distancia[MAXN];     // o array de distâncias à fonte
int processado[MAXN];    // o array que guarda se um vértice foi processado
int mapa[MAXN][MAXN];    // nossa matriz de adjacência
//---------------------

void Dijkstra(int S){
    
    for(int i = 1;i <= n;i++) distancia[i] = mapa[S][i];
    distancia[S] = 0;
    processado[S] = true;
    
    while(true){ // rodar "infinitamente"
        
        int davez = -1;
        int menor = INFINITO;
        
        // selecionamos o vértice mais próximo
        for(int i = 1;i <= n;i++)
            if(!processado[i] && distancia[i] < menor){
                davez = i;
                menor = distancia[i];
            }
        
        if(davez == -1) break; // se não achou ninguém, é o fim do algoritmo
        
        processado[davez] = true; // marcamos para não voltar para este vértice
        
        // agora, tentamos atualizar as distâncias
        for(int i = 1;i <= n;i++)
            distancia[i] = min(distancia[i], distancia[davez] + mapa[davez][i]);
    }
    
}

int main(){
    
    scanf("%d %d", &n, &m);
    scanf("%d %d", &cidade_succa, &cidade_noic);
    
    // inicializaremos a matriz para infinito em todas as casas
    for(int i = 1;i <= n;i++)
    for(int j = 1;j <= n;j++)
        mapa[i][j] = INFINITO;
    
    for(int i = 1;i <= m;i++){
        
        int x, y, tempo;
        scanf("%d %d %d", &x, &y, &tempo);
        
        // colocamos como recebendo esse valor mínimo para o caso
        // dois voos entre as mesmas cidades
        mapa[x][y] = min(mapa[x][y], tempo);
        mapa[y][x] = min(mapa[y][x], tempo);
    }
    
    Dijkstra(cidade_succa); // rodamos o Dijkstra
    printf("%d\n", distancia[cidade_noic]); // imprimimos a resposta
    
    return 0;
}