Problem:


大工の褒美

ある日、殿様は一人の大工に、「台風や地震が来たときに町人が避難できる、頑丈で大きな建物を造りなさい。」と命じました。しかし、その頑丈で大きな建物を完成させるには、大きな太い柱が必要です。町にそんな大きな柱はありません。そこで、大工は遠くの山里まで大きな柱を調達しに行くことになりました（大工は町から里山に行って、町に戻ってくる必要があります）。

大工の褒美は、殿様から受け取ったお金から柱の代金と交通費を差し引いた余りです。下の地図のように、山里に行くには、いろいろな町を通るたくさんの街道があり、2つの町をつなぐ街道はそれぞれ交通費が違います。大工の褒美を最大にするにはどのように街道をたどり調達すればよいでしょうか。最大となる大工の褒美を出力するプログラムを作成してください。ただし、町の数を n とすれば、各町は 1 から n までの整数で識別されます。2 つの町を直接つなぐ街道は 2 本以上ありません。

※ 矢印上の数字は、その方向に行くための交通費を示します。 

Input

入力は以下の形式で与えられます。

n
m
a1,b1,c1, d1
a2,b2,c2, d2
:
am,bm,cm, dm
s,g,V,P

1 行目に町の総数 n（ n ≤ 20）、2 行目に街道の総数 m (m ≤ 100) が与えられます。続く m 行に i 番目の街道の情報 ai, bi, ci, di (1 ≤ ai, bi ≤ n,  0 ≤ ci, di ≤ 1,000) が与えられます。ai, bi は街道 i がつないでいる町の番号、 ci は ai から bi への交通費、 di は bi から ai への交通費を表します。

最終行に大工が出発する町の番号 s、柱のある山里の番号 g、殿様から大工が受け取ったお金 V、柱の代金 P が与えられます。

Output

大工の褒美（整数）を１行に出力してください。

Sample Input

6
8
1,2,2,2 
1,3,4,3 
1,4,4,2 
2,5,3,2 
3,4,4,2 
3,6,1,2 
4,6,1,1 
5,6,1,2 
2,4,50,30

Output for the Sample Input

11



Sample input:
6
8
1,2,2,2
1,3,4,3
1,4,4,2
2,5,3,2
3,4,4,2
3,6,1,2
4,6,1,1
5,6,1,2
2,4,50,30


Sample output:
11

Submission status: Wrong Answer

Solution code:
import copy

def discomfort(dic, n):
    global expenses
    if expenses != None and sum(p_res) >= expenses:
        return
    if n == s_n and g_n in load:
        expenses = sum(p_res)
        Pirates.append(r-(sum(p_res)+p))
        return
    for v in dic[n]:
        p_res.append(p_dic[(n,v)])
        c_l_dic = copy.deepcopy(dic)
        c_l_dic[n].remove(v)
        c_l_dic[v].remove(n)
        load.append(v)
        discomfort(c_l_dic, v)
        del p_res[-1]
        del load[-1]

if __name__ == '__main__':
    t_c = int(raw_input())
    
    l_dic = {}
    p_dic = {}
    for i in range(input()):
        n1, n2, p1, p2 = map(int, raw_input().split(','))
        if not n1 in l_dic:
            l_dic[n1] = [n2]
            if not n2 in l_dic:
                l_dic[n2] = [n1]
            else:
                l_dic[n2].append(n1)
        else:
            l_dic[n1].append(n2)
            if not n2 in l_dic:
                l_dic[n2] = [n1]
            else:
                l_dic[n2].append(n1)
        p_dic[(n1,n2)] = p1
        p_dic[(n2,n1)] = p2
    
    s_n, g_n, r, p = map(int, raw_input().split(','))
    p_res = []
    load = [2]
    expenses = None
    Pirates = []
    discomfort(l_dic, s_n)
    print sorted(Pirates)[-1]

Submission status: Wrong Answer

Solution code:
import copy

def discomfort(dic, n):
    global expenses
    if expenses != None and sum(p_res) >= expenses:
        return
    if n == s_n and g_n in load:
        expenses = sum(p_res)
        Pirates.append(r-(sum(p_res)+p))
        return
    for v in dic[n]:
        c_l_dic = copy.deepcopy(dic)
        c_l_dic[n].remove(v)
        c_l_dic[v].remove(n)
        p_res.append(p_dic[(n,v)])
        load.append(v)
        discomfort(c_l_dic, v)
        del p_res[-1]
        del load[-1]

if __name__ == '__main__':
    t_c = int(raw_input())
    
    l_dic = {}
    p_dic = {}
    for i in range(input()):
        n1, n2, p1, p2 = map(int, raw_input().split(','))
        if not n1 in l_dic:
            l_dic[n1] = [n2]
            if not n2 in l_dic:
                l_dic[n2] = [n1]
            else:
                l_dic[n2].append(n1)
        else:
            l_dic[n1].append(n2)
            if not n2 in l_dic:
                l_dic[n2] = [n1]
            else:
                l_dic[n2].append(n1)
        p_dic[(n1,n2)] = p1
        p_dic[(n2,n1)] = p2
    
    s_n, g_n, r, p = map(int, raw_input().split(','))
    p_res = []
    load = [s_n]
    expenses = None
    Pirates = []
    discomfort(l_dic, s_n)
    print sorted(Pirates)[-1]

Submission status: Wrong Answer

Solution code:
INF = 10000000

n = int(input())
m = int(input())

table = [[-1 for i in range(n)] for j in range(n)]
visited = [False for i in range(n)]
cost = [INF for i in range(n)]

for l in range(m):
    a,b,c,d = [int(i) for i in input().split(",")]
    table[a-1][b-1] = c
    table[b-1][a-1] = d

s,g,V,P = [int(i) for i in input().split(",")]

visited[s-1] = True
cost[s-1] = 0
cnt = n-1
while cnt > 0:
    for i in range(n):
        if visited[i]:
            for j in range(n):
                if table[i][j] > 0 and visited[j] == False:
                    cost[j] = cost[i] + min(table[i][j], cost[j])
                    visited[j] = True
                    cnt -= 1

ans = cost[g-1]

for i in range(n):
    cost[i] = INF
    visited[i] = False

visited[g-1] = True
cost[g-1] = 0
cnt = n-1

while cnt > 0:
    for i in range(n):
        if visited[i]:
            for j in range(n):
                if table[i][j] > 0 and visited[j] == False:
                    cost[j] = cost[i] + min(table[i][j], cost[j])
                    visited[j] = True
                    cnt -= 1

ans += cost[s-1]

print(V-P-ans)

Submission status: Wrong Answer

Solution code:
# AOJ 0117 A reward for a Carpenter
# Python3 2018.6.21 bal4u

INF = 0x7fffffff

import heapq
def dijkstra(V, to, start, goal):
	dist = [INF]*V
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while len(Q):
		t, s = heapq.heappop(Q)
		if s == goal: break
		if dist[s] <= t: continue
		for i in to[s]:
			e, cost = i
			nt = t + cost
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))
	return dist[goal]

n = int(input())+1
to = [[] for i in range(n)]
for i in range(int(input())):
	a, b, c, d = list(map(int, input().split(',')))
	to[a].append((b, c))
	to[b].append((a, d))
s, g, V, P = list(map(int, input().split(',')))
if s == g: print(V-P)
else: print(V-P - dijkstra(n, to, s, g) - dijkstra(n, to, g, s))

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(start,goal,graph):

    INF = 2 << 20
    node_num = len(graph) 
    visited = [False] * node_num
    costs = [INF] * node_num
    pq = []
    costs[start] = 0
    #print costs[start]
    heapq.heappush(pq, [0,start])
    
    while not len(pq) == 0:
        cur_cost,cur_node = heapq.heappop(pq)

        if visited[cur_node]:
            continue
        if all(visited[1:]):
            break

        #print cur_cost,cur_node

        visited[cur_node] = True
        cost = INF
        for i in xrange(node_num):
            cost = min(graph[i][cur_node] + costs[i], cost)
        costs[cur_node] = cost
        #print costs
        
        for i in xrange(node_num):
            if not visited[i]:
                heapq.heappush(pq,[graph[cur_node][i],i])
    return costs[goal]

n = input()
m = input()
INF = 2 << 20
graph = [[INF] * (n+1) for _ in xrange(n+1)]
for _ in xrange(m):
    a,b,c,d = map(int,raw_input().split(","))
    #graph[from][to] = cost
    graph[a][b] = c
    graph[b][a] = d
home,shop,reward,price = map(int,raw_input().split(","))
graph[home][home] = 0
cost = dijkstra(home,shop,graph)
graph[home][home] = INF
graph[shop][shop] = 0
cost += dijkstra(shop,home,graph)
print reward - price - cost

Submission status: Wrong Answer

Solution code:
inf = 0x101010
def solve(start,goal):
	cost = [inf]*n
	visited = [False]*n
	cost[start] = 0
	while 1:
		min = inf
		next = -1
		visited[start] = True
		for i in range(n):
			if visited[i]: continue
			if graph[start][i]:
				d = cost[start] + graph[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
		start = next
		if next == -1: break
	return cost[goal]

n = input()
m = input()
graph = [[0]*n for i in range(n)]
for i in range(m):
	a,b,c,d = map(int,raw_input().split(","))
	graph[a-1][b-1] = c
	graph[b-1][a-1] = d
x1,x2,y1,y2 = map(int,raw_input().split(","))
print y1-y2-solve(x1-1,x2-1)-solve(x2-1,x1-1)

Submission status: Accepted

Solution code:
def f(x1, x2):
  W = [[i, 1001] for i in range(n)]
  W[x1] = [x1, 0]
  W[x2] = [x2, 2000]
  i=0
  while 1:
    A = sorted(W, key = lambda x:x[1])
    p1, w1 = A[i]
    if p1 == x2: break
    for p2, w2 in A[i + 1:]:
      way=(p1, p2)
      if way in cost:
        tmp = w1 + cost[way]
        W[p2] = [p2, min([w2, tmp])]
    i += 1
  return W[x2][1]

n = int(raw_input())
m = int(raw_input())
cost = {}
for _ in [0] * m:
  a, b, c, d = map(int, raw_input().split(","))
  cost[(a-1, b-1)] = c
  cost[(b-1, a-1)] = d
x1, x2, y1, y2 = map(int, raw_input().split(","))
x1 -= 1
x2 -= 1
print y1 - y2 - f(x1, x2) - f(x2, x1)

Submission status: Accepted

Solution code:
def f(x1, x2):
  W = [[i, 1001] for i in range(n)]
  W[x1] = [x1, 0]
  W[x2] = [x2, 2000]
  G = range(n)
  while 1:
    A = sorted([W[e] for e in G], key = lambda x:x[1])
    p1, w1 = A[0]
    G.remove(p1)
    if p1 == x2: break
    for p2, w2 in A[1:]:
      way=(p1, p2)
      if way in cost:
        W[p2] = [p2, min([w2, w1+cost[way]])]
  return W[x2][1]
def g(): return map(int, raw_input().split(","))

n = int(raw_input())
m = int(raw_input())
cost = {}
for _ in [0] * m:
  a, b, c, d = g()
  cost[(a-1, b-1)] = c
  cost[(b-1, a-1)] = d
x1, x2, y1, y2 = g()
x1 -= 1
x2 -= 1
print y1-y2-f(x1,x2)-f(x2,x1)

Submission status: Accepted

Solution code:
def f(x1, x2):
  W=[[i,1000] for i in range(n)]
  W[x1]=[x1,0]
  W[x2]=[x2,2000]
  G = range(n)
  while 1:
    A = sorted([W[e] for e in G], key=lambda x: x[1])
    p1, w1 = A[0]
    G.remove(p1)
    if p1==x2: break
    for p2, w2 in A[1:]:
      way=(p1, p2)
      if way in cost: W[p2] = [p2, min([w2, w1+cost[way]])]
  return W[x2][1]

def g(): return map(int, raw_input().split(","))

n=int(raw_input())
m=int(raw_input())
cost={}
for _ in [0]*m:
  a,b,c,d=g()
  a-=1
  b-=1
  cost[(a,b)]=c
  cost[(b,a)]=d
x1,x2,y1,y2=g()
x1-=1
x2-=1
print y1-y2-f(x1,x2)-f(x2,x1)

Submission status: Accepted

Solution code:
def f(x1, x2):
  W=[[i,1000] for i in range(n)]
  W[x1]=[x1,0]
  W[x2]=[x2,2000]
  G = range(n)
  while 1:
    A = sorted([W[e] for e in G], key=lambda x: x[1])
    p1, w1 = A[0]
    G.remove(p1)
    if p1==x2: break
    for p2, w2 in A[1:]:
      way=(p1, p2)
      if way in cost:
        W[p2] = [p2, min([w2, w1 + cost[way]])]
  return w1

def g(): return map(int, raw_input().split(","))

n=int(raw_input())
m=int(raw_input())
cost={}
for _ in [0]*m:
  a,b,c,d=g()
  a-=1
  b-=1
  cost[(a,b)]=c
  cost[(b,a)]=d
x1,x2,y1,y2=g()
x1-=1
x2-=1
print y1-y2-f(x1,x2)-f(x2,x1)

Submission status: Accepted

Solution code:
def f(x1, x2):
  W=[[i,1000] for i in range(n)]
  W[x1]=[x1,0]
  W[x2]=[x2,2000]
  G = range(n); G=G[x2:]+G[:x2]
  while 1:
    A = sorted([W[e] for e in G], key=lambda x: x[1])
    p1, w1 = A[0]
    G.remove(p1)
    if p1==x2: break
    for p2, w2 in A[1:]:
      way=(p1, p2)
      if way in cost:
        W[p2] = [p2, min([w2, w1 + cost[(p1,p2)]])]
  return w1

def g(): return map(int, raw_input().split(","))

n=int(raw_input())
m=int(raw_input())
cost={}
for _ in [0]*m:
  a,b,c,d=g()
  a-=1
  b-=1
  cost[(a,b)]=c
  cost[(b,a)]=d
x1,x2,y1,y2=g()
x1-=1
x2-=1
print y1-y2-f(x1,x2)-f(x2,x1)

Submission status: Accepted

Solution code:
INF = 1000000

n = int(input())
m = int(input())
cost = [[INF] * (n + 1) for i in range(n + 1)]

for i in range(m):
    ai, bi, ci, di = (int(s) for s in input().split(','))
    cost[ai][bi] = ci
    cost[bi][ai] = di

x1, x2, y1, y2 = (int(s) for s in input().split(','))

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                cost[i][j] = cost[i][k] + cost[k][j]

print(y1 - y2 - cost[x1][x2] - cost[x2][x1])

Submission status: Accepted

Solution code:
INF = 1000000


def bellman_ford(graph, source):
    lg = len(graph)
    unused = list(range(lg))
    d = [INF] * (lg)
    d[source] = 0

    while unused:
        v = min(unused, key=lambda u: d[u])
        unused.remove(v)
        for u in range(n + 1):
            d[u] = min(d[u], d[v] + graph[v][u])

    return d

n = int(input())
m = int(input())

cost = [[INF] * (n + 1) for i in range(n + 1)]
for i in range(m):
    ai, bi, ci, di = map(int, input().split(','))
    cost[ai][bi] = ci
    cost[bi][ai] = di

x1, x2, y1, y2 = map(int, input().split(','))

d_go = bellman_ford(cost, x1)[x2]
d_back = bellman_ford(cost, x2)[x1]

print(y1 - y2 - d_go - d_back)

Submission status: Accepted

Solution code:
INF = 1e12


def dijkstra(graph, source):
    lg = len(graph)
    unused = list(range(lg))
    d = [INF] * (lg)
    d[source] = 0

    while unused:
        v = min(unused, key=lambda u: d[u])
        unused.remove(v)
        for u in range(n + 1):
            d[u] = min(d[u], d[v] + graph[v][u])

    return d

n = int(input())
m = int(input())

cost = [[INF] * (n + 1) for i in range(n + 1)]
for i in range(m):
    ai, bi, ci, di = map(int, input().split(','))
    cost[ai][bi] = ci
    cost[bi][ai] = di

x1, x2, y1, y2 = map(int, input().split(','))

d_go = dijkstra(cost, x1)[x2]
d_back = dijkstra(cost, x2)[x1]

print(y1 - y2 - d_go - d_back)

Submission status: Accepted

Solution code:
V = int(input())
E = int(input())
dist = [[float('inf')] * V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for _ in range(E):
    a, b, c, d = map(int, input().split(','))
    dist[a-1][b-1], dist[b-1][a-1] = c, d
fr, to, money, cost = map(int, input().split(','))
for k in range(V):
    for i in range(V):
        for j in range(V):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
print(money-cost-dist[fr-1][to-1]-dist[to-1][fr-1])

Submission status: Accepted

Solution code:
import copy

def discomfort(dic, n):
    global expenses, c
    if expenses != None and sum(p_res) >= expenses:
        return
    if n == c:
        if n == g_n:
            c = s_n
            discomfort(l_dic, g_n)
            c = g_n
            return
        else:
            expenses = sum(p_res)
            Pirates.append(r-(sum(p_res)+p))
            return
    for v in dic[n]:
        c_l_dic = copy.deepcopy(dic)
        c_l_dic[n].remove(v)
        c_l_dic[v].remove(n)
        p_res.append(p_dic[(n,v)])
        load.append(v)
        discomfort(c_l_dic, v)
        del p_res[-1]
        del load[-1]

if __name__ == '__main__':
    t_c = int(raw_input())
    
    l_dic = {}
    p_dic = {}
    for i in range(input()):
        n1, n2, p1, p2 = map(int, raw_input().split(','))
        if not n1 in l_dic:
            l_dic[n1] = [n2]
            if not n2 in l_dic:
                l_dic[n2] = [n1]
            else:
                l_dic[n2].append(n1)
        else:
            l_dic[n1].append(n2)
            if not n2 in l_dic:
                l_dic[n2] = [n1]
            else:
                l_dic[n2].append(n1)
        p_dic[(n1,n2)] = p1
        p_dic[(n2,n1)] = p2
    
    s_n, g_n, r, p = map(int, raw_input().split(','))
    c = g_n
    Pirates = []
    p_res = []
    load = [s_n]
    expenses = None
    discomfort(l_dic, s_n)
    print sorted(Pirates)[-1]

Submission status: Accepted

Solution code:
import copy

def discomfort(dic, n):
    global Pirates, expenses, c
    if expenses != None and sum(p_res) >= expenses:
        return
    if n == c:
        if n == g_n:
            c = s_n
            discomfort(l_dic, g_n)
            c = g_n
            return
        else:
            expenses = sum(p_res)
            Pirates = r-(sum(p_res)+p)
            return
    for v in dic[n]:
        c_l_dic = copy.deepcopy(dic)
        c_l_dic[n].remove(v)
        c_l_dic[v].remove(n)
        p_res.append(p_dic[(n,v)])
        load.append(v)
        discomfort(c_l_dic, v)
        del p_res[-1]
        del load[-1]

if __name__ == '__main__':
    t_c = int(raw_input())
    
    l_dic = {}
    p_dic = {}
    for i in range(input()):
        n1, n2, p1, p2 = map(int, raw_input().split(','))
        if not n1 in l_dic:
            l_dic[n1] = [n2]
            if not n2 in l_dic:
                l_dic[n2] = [n1]
            else:
                l_dic[n2].append(n1)
        else:
            l_dic[n1].append(n2)
            if not n2 in l_dic:
                l_dic[n2] = [n1]
            else:
                l_dic[n2].append(n1)
        p_dic[(n1,n2)] = p1
        p_dic[(n2,n1)] = p2
    
    s_n, g_n, r, p = map(int, raw_input().split(','))
    c = g_n
    Pirates = 0
    p_res = []
    load = [s_n]
    expenses = None
    discomfort(l_dic, s_n)
    print Pirates

Submission status: Accepted

Solution code:
import sys

def dijkstra(nodes, start, goal, matrix):
  defnode = [False] * (nodes+1)
  cost = [sys.maxint] * (nodes+1)
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in xrange(1, nodes+1):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(1, nodes+1):
      if defnode[i]:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    if minnode == goal:
      return cost[goal]
    node = minnode

n = int(raw_input())
m = int(raw_input())
matrix = [[sys.maxint]*(n+1) for i in xrange(n+1)]
for i in xrange(m):
  a, b, c, d = map(int, raw_input().split(","))
  matrix[a][b] = c
  matrix[b][a] = d
s, g, V, P = map(int, raw_input().split(","))
answer = V - P - dijkstra(n, s, g, matrix) - dijkstra(n, g, s, matrix)
print answer

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
from collections import defaultdict

n = int(input())
m = int(input())

# Map
M = defaultdict(list)

for i in range(m):
    a, b, c, d = list(map(int, input().split(',')))
    a -= 1
    b -= 1
    M[a].append((b, c))
    M[b].append((a, d))

s, g, V, P = list(map(int, input().split(',')))
s -= 1
g -= 1

def min_dist(Q, dists):
    min_v = float('inf')
    min_i = None

    for i in Q:
        if dists[i] < min_v:
            min_v = dists[i]
            min_i = i
    return min_v, min_i

def dijkstra(i, j, M):
    """return cost from i to j"""

    n = len(M)
    dists = [float('inf')] * n
    dists[i] = 0

    Q = [i for i in range(n)]
    while Q:
        min_dist_index = min_dist(Q, dists)[1]
        Q.remove(min_dist_index)

        for idx, cost in M[min_dist_index]:
            if dists[idx] > dists[min_dist_index] + cost:
                dists[idx] = dists[min_dist_index] + cost
    return dists[j]

res0 = dijkstra(s, g, M)
res1 = dijkstra(g, s, M)

print(V - P - res0 - res1)

Submission status: Accepted

Solution code:
# Aizu Problem 0117: A reward for a Carpenter
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

# -----------------------------------------------------------------------
# Defining directed graph class: 
# -----------------------------------------------------------------------

class DirectedGraph:
    """An DirectedGraph g contains a dictionary (g.neighbor_dict) which
    maps node identifiers (keys) to lists of neighboring nodes (values).
    g.neighbor_dict[node] returns a list [node2, node3, node4] of neighbors.
    Node identifiers can be any non-mutable Python type (e.g., integers,
    tuples, strings, but not lists)."""

    def __init__(self):
        """ UndirectedGraph() creates an empty graph g.
        g.neighbor_dict starts as an empty dictionary.  When nodes are
        added, the corresponding values need to be inserted into lists."""
        self.neighbor_dict = {}
        self.explored_dict = {}

 
    def HasNode(self, node):
        """Does not use the dict.keys() method, which would generate a 
        new list of all nodes each time this is called."""
        return node in self.neighbor_dict

    def AddNode(self, node):
        """ Uses HasNode(node) to determine if node has already been added.
            Optional argument position is for later drawing. Positions are
            in range [0.0, 1.0] and represent fractions of drawing window size.
            Color is also for drawing.
        """
        if( self.HasNode(node) ):
            return
        self.neighbor_dict[node] = []
        self.explored_dict[node] = False
        
    def AddEdge(self, node1, node2, length):
        """
    Add node1 and node2 to network first if necessary.
    Adds new edge node1 -> node2 with length 'length'
    """
        if( not self.HasNode(node1) ):
            self.AddNode(node1)
        if( not self.HasNode(node2) ):
            self.AddNode(node2)
        neighbors = self.neighbor_dict[node1]
        neighbors.append((node2, length))
        self.neighbor_dict[node1] = neighbors


    def GetExplored(self, node):
        """ Get explorationn status of node """
        return self.explored_dict[node]
        

    def GetNextUnexploredNeighbor(self, node):
        """ Get a neighbor node which is still unexplored. If none exists,
            return -1 """
        for neighbor in self.GetNeighbors(node):
            if( not self.GetExplored(neighbor) ):
                return neighbor
        return -1
        
    def SetExplored(self, node, value):
        """ Mark node as explored """
        self.explored_dict[node] = value
        
    def GetNodes(self):
        """g.GetNodes() returns all nodes (keys) in neighbor_dict"""
        return self.neighbor_dict.keys()

    def GetNeighbors(self, node):
        """g.GetNeighbors(node) returns a copy of the list of neighbors of
        the specified node.  A copy is returned (using the [:] operator) so
        that the user does not inadvertently change the neighbor list."""
        result = []
        for neighbor in self.neighbor_dict[node]:
            result.append(neighbor[0])
        return result


    def GetEdgeLength(self, node1, node2):
        """ Get length of edge from node1 to node2 """
        result = 9999999999999999
        neighbors = self.neighbor_dict[node1]
        #print neighbors
        for neighbor in neighbors:
            if( neighbor[0] == node2 ):
                return neighbor[1]
        return result

    
    def GetNumExploredNodes(self):
        """ Return number of explored nodes """
        num = 0
        for key, value in self.explored_dict.items():
            if( value ): num += 1
        return num

    
    #def GetPosition(self, node):
    #    """ Returns drawing position of node
    #    """
    #    return self.positions[node]
    
    #def SetColor(self, node, color):
    #    """ Returns color of node
    #    """
    #    self.colors[node] = color
    
    #def GetColor(self, node):
    #    """ Returns color of node
    #    """
    #    return self.colors[node]
    
    def GetDegree(self, node):
        """ Returns degree of node, i.e. number of edges connected to it
        """
        return len(self.GetNeighbors(node))
    
    def GetOrderedDegrees(self):
        """ Returns list of nodes, ordered by degree
        """
        result = []
        nodes = self.GetNodes()
        for node in nodes:
            result.append((node, self.GetDegree(node)))
        return sorted(result, key=lambda result: result[1], reverse=True)

    def GetAllEdges(self):
        """ Returns list of all edges
        """
        result = []
        nodes = self.GetNodes()
        for node in nodes:
            neighbors = self.GetNeighbors(node)
            for neighbor in neighbors:
                result.append((node, neighbor))
        return result


def dijkstra(graph, s):
    """ Implement 'naive' Dijktstra's algorithm (no heaps) for graph 'graph'
        and start vertex s """
    n = len(graph.GetNodes())
    #print "Dijkstra: # nodes =", n
    X = [s]      # vertices processed so far
    A = {}      # computed shortest path distances
    A[s] = 0    # distance of start vertex to itself

    # main loop:
    while( len(A) < n ):
        dijkstra_greedy = 999999999999999999999
        v_star = -1
        w_star = -1
        for v in X:
            for w in graph.GetNeighbors(v):
                if( w not in X ):
                    current_dist = A[v] + graph.GetEdgeLength(v, w)
                    if( current_dist < dijkstra_greedy ):
                        v_star = v
                        w_star = w
                        dijkstra_greedy = current_dist
        X.append(w_star)
        A[w_star] = dijkstra_greedy
    # set default distances for unvisited nodes:
    for node in graph.GetNodes():
        if( node not in A.keys() ):
            A[node] = 1000000
    return A                

G = DirectedGraph()
n = int(input())
for city in range(1, n + 1):
    G.AddNode(city)
m = int(input())
for road in range(m):
    city1, city2, cost1, cost2 = [int(_) for _ in input().split(',')]
    G.AddEdge(city1, city2, cost1)
    G.AddEdge(city2, city1, cost2)
source, target, money, price = [int(_) for _ in input().split(',')]
d = dijkstra(G, source)
cost1 = d[target]
d = dijkstra(G, target)
cost2 = d[source]
print(money - price - cost1 - cost2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117

"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


def main(args):
    n = int(input())
    m = int(input())
    dp = [[float('inf')]*(n+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][i] = 0
    for _ in range(m):
        a, b, c, d = [int(x) for x in input().split(',')]
        dp[a][b] = c
        dp[b][a] = d
    s, g, V, P = [int(x) for x in input().split(',')]
    # print(dp)
    warshallFloyd(n+1, dp)
    # print(dp)

    print(V - dp[s][g] - dp[g][s] - P)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117
AC
"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    n = int(input())
    m = int(input())
    dp = [[float('inf')]*(n) for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for _ in range(m):
        a, b, c, d = [int(x) for x in input().split(',')]
        dp[a-1][b-1] = c
        dp[b-1][a-1] = d
    s, g, V, P = [int(x) for x in input().split(',')]

    warshallFloyd(n, dp)

    print(V - dp[s-1][g-1] - dp[g-1][s-1] - P)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# The question itself is not diffifult, but the website only 
# tested my code with two cases, so I am not sure whether the 
# "accepted" is trustworthy.

# Note: math.inf > math.inf -> False

import math
V = int(input())
E = int(input())
fees = [[math.inf] * V for i in range(V)]
for i in range(V): 
	fees[i][i] = 0
for i in range(E):
	a, b, c, d = map(int, input().split(','))
	fees[a-1][b-1] = c
	fees[b-1][a-1] = d
start, end, funding, cost = map(int, input().split(','))
for i in range(V):
	for j in range(V):
		for k in range(V):
			if (fees[j][k] > fees[j][i] + fees[i][k]):
				fees[j][k] = fees[j][i] + fees[i][k]
if (fees[start-1][end-1]==math.inf or fees[end-1][start-1]==math.inf):
	print(0)
else:
	print(funding-cost-fees[start-1][end-1]-fees[end-1][start-1])

Submission status: Accepted

Solution code:
n = int(input())
m = int(input())

dp = [[float('inf') for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = 0

for _ in range(m):
    a, b, c, d = map(int, input().split(','))
    dp[a - 1][b - 1] = c
    dp[b - 1][a - 1] = d

for k in range(n):
    for i in range(n):
        for j in range(n):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

s, g, v, p = map(int, input().split(','))

print(v - p - dp[s-1][g-1] - dp[g-1][s-1])

Submission status: Accepted

Solution code:
class Graph():

    from collections import namedtuple
    __Pair = namedtuple("Pair", "cost point")

    def __init__(self, townCount):
        self.__townCount = townCount
        self.__adjacencyList = [[] for _ in range(townCount)]

    def GetPath(self, beginPoint, endPoint, cost):
        item = self.__Pair(cost, endPoint)
        self.__adjacencyList[beginPoint].append(item)

    def Dijkstra(self, beginPoint):

        from sys import maxsize as MaxValue
        from queue import PriorityQueue
        stateTable = {"NotVisited": 0, "Stay": 1, "Visited": 2}

        # 初期化
        pq = PriorityQueue()
        costTable = [MaxValue for _ in range(self.__townCount)]
        visitState = [stateTable["NotVisited"]
                      for _ in range(self.__townCount)]

        # 処理
        costTable[beginPoint] = 0
        pq.put_nowait(self.__Pair(0, beginPoint))

        while not pq.empty():

            minItem = pq.get_nowait()
            minPoint, minCost = minItem.point, minItem.cost

            visitState[minPoint] = stateTable["Visited"]

            if minCost <= costTable[minPoint]:

                for cost, point in self.__adjacencyList[minPoint]:
                    if visitState[point] != stateTable["Visited"]:

                        if costTable[minPoint] + cost < costTable[point]:
                            costTable[point] = costTable[minPoint] + cost
                            visitState[point] = stateTable["Stay"]
                            pq.put_nowait(self.__Pair(costTable[point], point))

        return costTable


# main process
townCount = int(input())
wayCount = int(input())

graph = Graph(townCount)

for lp in range(wayCount):
    begin, end, cost1, cost2 = [int(item) for item in input().split(",")]
    begin -= 1
    end -= 1
    graph.GetPath(begin, end, cost1)
    graph.GetPath(end, begin, cost2)


beginPoint, endPoint, budget, pillarCost = [
    int(item) for item in input().split(",")]

beginPoint -= 1
endPoint -= 1

leaveCost = graph.Dijkstra(beginPoint)
returnCost = graph.Dijkstra(endPoint)

result = budget - pillarCost - leaveCost[endPoint] - returnCost[beginPoint]

print(result)

Submission status: Accepted

Solution code:
#dijkstra

from heapq import heappop as pop
from heapq import heappush as push

INF = 10 ** 20

n = int(input())
m = int(input())

edges = [[] for _ in range(n)]

for _ in range(m):
  a, b, c, d = map(int, input().split(","))
  a, b = a - 1, b - 1
  edges[a].append((b, c))
  edges[b].append((a, d))

s, g, v, p = map(int, input().split(","))
s, g = s - 1, g - 1

def dij(s, g):
  que = [(0, s)]
  costs = [INF for _ in range(n)]
  costs[s] = 0
  
  while que:
    cost, num = pop(que)
    if num == g:
      return cost
    for edge in edges[num]:
      to, fee = edge
      if costs[to] > cost + fee:
        costs[to] = cost + fee
        push(que, (cost + fee, to))

print(v - p - dij(s, g) - dij(g, s))

Submission status: Accepted

Solution code:
INF = 10000000

n = int(input())
m = int(input())

table = [[INF for i in range(n)] for j in range(n)]

for l in range(m):
    a,b,c,d = [int(i) for i in input().split(",")]
    table[a-1][b-1] = c
    table[b-1][a-1] = d
s,g,V,P = [int(i) for i in input().split(",")]

visited = [False for i in range(n)]
cost = [INF for i in range(n)]

cost[s-1] = 0

while True:
    v = -1
    for i in range(n):
        if visited[i] == False and (v == -1 or cost[i] < cost[v]):
            v = i
    if v == -1:
        break
    visited[v] = True
    for i in range(n):
        cost[i] = min(cost[i], cost[v] + table[v][i])

ans = cost[g-1]

visited = [False for i in range(n)]
cost = [INF for i in range(n)]

cost[g-1] = 0

while True:
    v = -1
    for i in range(n):
        if visited[i] == False and (v == -1 or cost[i] < cost[v]):
            v = i
    if v == -1:
        break
    visited[v] = True
    for i in range(n):
        cost[i] = min(cost[i], cost[v] + table[v][i])

ans += cost[s-1]

print(V-P-ans)