Frete OBI f2p2 2017 comentário NOIC

frete.cpp

#include <bits/stdc++.h>

//define MAX e INF
#define INF 0x3f3f3f3f
#define MAX 110

using namespace std;

//declara as variáveis decritas no problema
int n, m;
int a, b, c;

//e a matriz de adjacência
int dist[MAX][MAX];

void floyd(){
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
}

int main(){
	//lê a quantidade de vértices e arestas
	scanf("%d %d", &n, &m); 
	
	//inicializa as distâncias entre os vértices como infinito 
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			dist[i][j]=INF;
	
	for(int i=0; i<m; i++){
		//lê as arestas
		scanf("%d %d %d", &a, &b, &c);
		
		//e atualiza os pesos na matriz
		dist[a][b]=c;
		dist[b][a]=c;
	}
	
	//algoritmo de Floyd-Warshall
	floyd();
	
	//imprime a menor distância entre 1 e n
	printf("%d\n", dist[1][n]);
}