ENGARRAF

gistfile1.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TAM 100
#define INF (0x3f3f3f3f)

int city[TAM][TAM], custo[TAM], visitados[TAM], n;

void dijkstra(int s, int d) {
    int i, atual, minimo;
    custo[s] = 0;
    atual = s;
    while (atual != d) {
        for (i = 0; i < n; i++){
            if (city[atual][i] != INF){
                if (custo[atual] + city[atual][i] < custo[i])
                    custo[i] = custo[atual] + city[atual][i];
            }
        }
        minimo = INF;
        visitados[atual] = 1;
        for (i = 0; i < n; i++)
            if ((custo[i] <= minimo) && (!visitados[i]))
                minimo = custo[i], atual = i;
        if (minimo >= INF)
            custo[d]=INF;
    }
}

inline void readn( register int *n ) {
    int sign = 1;
    register char c;
	static char buffer[1000000];
	static char *p;

    *n = 0;

	if( p == NULL ) {
	 	fread(buffer, 1, 1000000, stdin);
	    p = buffer;
	}

    while( ( c = *p++ ) != '\n' ) {
        switch( c ) {
			case '-' : sign = -1; break;
            case ' ': goto hell;
            case '\n': goto hell;
            default: (*n) *= 10; (*n) += ( c - '0' ); break;
        }
    }
hell:
    (*n)*=sign;
}

int main() {
    int m,i,j,t,s,d;
    while(readn(&n), n!=0){
        readn(&m);
        memset(city,INF,sizeof(city));
        memset(visitados,0,sizeof(visitados));
        memset(custo,INF,sizeof(custo));
        while(m--){            
            readn(&i);
            readn(&j);
            readn(&t);
            city[i-1][j-1] = t;
        }
        readn(&s);
        readn(&d);
        dijkstra(s-1,d-1);
        if(custo[d-1] == INF) printf("-1\n");
        else printf("%d\n",custo[d-1]);
    }
    return 0;
}