AOJ_0117 A reward for a Carpenter

問題
解法
有向グラフの最短経路を求める問題。
ワーシャルフロイド法をつかえば十分はやく求まる。

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 1 << 29;
const int MAX_N = 21;
int G[MAX_N][MAX_N];
int N, s, g;
int HOUBI, HASHIRA;
int w(){
	for(int k = 0; k < N; k++){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
			}
		}
	}
	return G[s][g] + G[g][s];
}
int main(){
	int m;
	int a, b, c, d;
	scanf("%d", &N);
	scanf("%d", &m);
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			G[i][j] = INF;	//初期化
	}}
	for(int i = 0; i < m; i++){
		scanf("%d, %d, %d, %d", &a, &b, &c, &d);
		a--; b--;
		G[a][b] = c;
		G[b][a] = d;
	}
	scanf("%d, %d, %d, %d", &s, &g, &HOUBI, &HASHIRA);
	s--; g--;
	printf("%d\n", HOUBI - HASHIRA - w());
	return 0;
}