AOJ Volume1 0117: A reward for a Carpenter

街の数が20以下なのでワーシャル-フロイド法で

/************************************
* 2012/07/05                        *
* AOJ Volume1 0117                  *
* A reward for a Carpenter          *
* crane                             *
*************************************/

#include <iostream>
#include <cstdio>
using namespace std;
#define MAX_N 1000
#define MAX_M 21
int field[MAX_M][MAX_M];
int n,m;
void warshall_floyd();

int main(){
  
    int a,b,c,d;
    cin >> n >> m;
  
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            field[i][j]=MAX_N;
    for(int i=0; i<m; i++){
        scanf("%d,%d,%d,%d",&a,&b,&c,&d);
        field[a][b] = c;
        field[b][a] = d;
    }
    warshall_floyd();
    int x1,x2,y1,y2;
    scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
    cout << y1-field[x1][x2]-field[x2][x1]-y2 << endl;
  
}

void warshall_floyd(){
        for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                field[i][j]=min(field[i][j],field[i][k]+field[k][j]);

}