81. 벨만-포드 알고리즘

문제

N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 한 도시에서 다른 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하세요.

입력설명

첫 번째 줄에는 도시의 수N(N<=100)과 도로수 M(M<=200)가 주어지고, M줄에 걸쳐 도로정보 와 비용이 주어진다. 만약 1번 도시와 2번도시가 연결되고 그 비용이 13이면 “1 2 13”으로 주어진다. 그 다음 마지막 줄에 출발도시와 도착도시가 주어진다.

출력설명

출발도시에서 도착도시까지 가는데 걸리는 최소비용을 출력한다. 음의 사이클이 존재할 경우 -1를 출력한다.

입력예제

5 7
1 2 5
1 3 4
2 3 -3
2 5 13
3 4 5
4 2 3
4 5 7
1 5

출력예제

14

---

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int distances[101];
struct Edge{
	int s;
	int e;
	int value;
	Edge(int a, int b, int c){
		s = a;
		e = b;
		value = c;
	}
};

int main(){
	freopen("input.txt", "rt", stdin);
	vector<Edge> Ed;
	int i, n, m, a, b, c, j, s, e;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		Ed.push_back(Edge(a, b, c));
	}
	for(i=1; i<=n; i++){
		distances[i] = 2147000000;
	}
	scanf("%d %d", &s, &e);
	distances[s] = 0;
	for(i=1; i<n; i++){
		for(j=0; j<Ed.size(); j++){
			int u = Ed[j].s;
			int v = Ed[j].e;
			int w = Ed[j].value;
			if(distances[u]!=2147000000 && distances[u]+w<distances[v]){
				distances[v] = distances[u] + w;
			}
		}
	}
	for(j=0; j<Ed.size(); j++){
		int u = Ed[j].s;
		int v = Ed[j].e;
		int w = Ed[j].value;
		if(distances[u]!=2147000000 && distances[u]+w<distances[v]){
			printf("-1");
			exit(0);
		}
	}
	printf("%d\n", distances[e]);
	
	return 0;
}