0117 - A reward for a Carpenter

#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

#define MAX_V 20
#define INF (1<<29)

typedef pair<int,int> P_II;

struct edge	{
	int to, cost;
	edge(int a, int b)	{to=a; cost=b;}
};

vector<edge> G[MAX_V];

int Dijkstra(int start, int goal, int V)	{
	int d[MAX_V];
	priority_queue< P_II, vector<P_II>, greater<P_II> > que;

	fill(d,d+V,INF);
	d[start]=0;
	que.push( P_II(0,start) );
	while ( !que.empty() )	{
		P p=que.top(); que.pop();
		int v=p.second;
		if (d[v] < p.first)	continue;
		for (int i=0; i<G[v].size(); ++i)	{
			edge e=G[v][i];
			if (d[e.to] > d[v]+e.cost)	{
				d[e.to]=d[v]+e.cost;
				que.push( P(d[e.to],e.to) );
			}
		}
	}
	return d[goal];
}

void Slove(int n)	{
	int m, a, b, c, d, x1, x2, y1, y2;

	cin >> m;
	for (int i=0; i<m; ++i)	{
		scanf ("%d,%d,%d,%d", &a, &b, &c, &d);
		G[a-1].push_back( edge(b-1,c) );
		G[b-1].push_back( edge(a-1,d) );
	}
	scanf ("%d,%d,%d,%d", &x1, &x2, &y1, &y2);
	cout << y1-Dijkstra(x1-1,x2-1,n)-Dijkstra(x2-1,x1-1,n)-y2 << endl;
}

int main(void)	{
	int n;

	cin >> n;
	Slove(n);
	return 0;
}