117-A Reward for a Carpenter

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0117&lang=jp
実装が楽なワーシャルフロイドのアルゴリズムで解答。
典型問題？

#define INF 99999;
#define MAX_V 20
int V;
int dist[MAX_V][MAX_V];
void warshall_floyd(){
	for(int k=0;k<V;k++){
		for(int i=0;i<V;i++){
			for(int j=0;j<V;j++){
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
}

int main(int argc,char *argv[]){
	scanf("%d",&V);
	int m;
	scanf("%d",&m);
	int a,b,c,d;
	for(int i=0;i<MAX_V;i++){
		for(int j=0;j<MAX_V;j++){
			if(i!=j) dist[i][j]=INF;
			if(i==j) dist[i][j]=0;
		}
	}
	for(int i=0;i<m;i++){
		scanf("%d,%d,%d,%d",&a,&b,&c,&d);
		dist[a-1][b-1]=c;
		dist[b-1][a-1]=d;
	}
	warshall_floyd();
	scanf("%d,%d,%d,%d",&a,&b,&c,&d);
	printf("%d\n",c-(d+dist[a-1][b-1]+dist[b-1][a-1]));
	return 0;
}