Resuelve https://omegaup.com/arena/problem/masbaratos

mas-baratos.cpp

// NOTE: Code from my early beginnings (circa 2010).
#include<iostream>
#include <cstdio>
#define MAX_V 1001
#define INFINITO 1000000	//Cualquier valor mas grande que los pesos que usemos

void InicializaArreglos();
void Dijkstra(int NodoInicial);
int AunEncolado(int nodo);
int DevuelveMinimo();

//Variables globales
int G[MAX_V][MAX_V];
int D[MAX_V];	//Distancias
int C[MAX_V];	//Caminos
int IE[MAX_V];	//Indices sellados
int V,A,K,Elementos;

using namespace std;
int main()
{
    int u,u2,index,I,J, peso,min;
    //freopen("entrada.in","r",stdin);	//Para las pruebas
    scanf("%d %d %d",&V, &K, &A);

    for(u = 0; u<A; u++){
        scanf("%d %d %d",&I,&J,&peso);
        G[I-1][J-1] = peso;	//Es un grafo dirigido
    }

    Dijkstra(1);

    /*for(u = 0; u<V; u++)
        printf("%d ",D[u]);
    printf("\n\n");
    */



    for(u = 0; u<K; u++){
        min = INFINITO;
        for(u2 = 0; u2<V; u2++){
            if(D[u2]<min){
                min = D[u2];
                index = u2;
            }
        }
        printf("%d ",index+1);
        D[index] = INFINITO;
    }

    return 0;
}

void InicializaArreglos()
{
    int indice;
    for(indice = 0; indice<V; indice++){
        IE[indice] = indice;
        D[indice] = INFINITO;
    }
}
//------------------------------------------------------------------------------
void Dijkstra(int NodoInicial)
{
    int vi, vj;
    InicializaArreglos();
    Elementos = V;
    D[NodoInicial-1] = 0;
    while(Elementos>0){
        vi = DevuelveMinimo();
        for(vj = 0 ;vj<V; vj++){
            //Si existe una nodo adyacente
            if(G[vi][vj]>0 && D[vi] + G[vi][vj]<D[vj] && AunEncolado(vj)){
                D[vj] = D[vi] + G[vi][vj];
            }
        }
    }
}
//------------------------------------------------------------------------------
int AunEncolado(int nodo)
{
    int e;
    for(e = 0; e<Elementos; e++){
        if(IE[e] == nodo)
            return 1;
    }
    return 0;
}
//------------------------------------------------------------------------------
int DevuelveMinimo()
{
    int a, min, i;
    min = INFINITO;
    for(a = 0; a<Elementos; a++){
        if(D[IE[a]]<min){
            min = D[IE[a]];
            i = IE[a];
        }
    }
    IE[i] = IE[Elementos - 1];
    IE[Elementos - 1] = -1;
    Elementos--;	//Un elementos menos
    return i;		//Retorno el valor del nodo al cual tiene la menor distancia
}