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: Accepted

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

roads = [[float('inf') for _ in range(n)] for _ in range(n)]

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

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

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

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

Submission status: Accepted

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: Accepted

Solution code:
def floyd(P,m):
    for k in range(m):
        for i in range(m):
            for j in range(m):
                P[i][j]=min(P[i][j],P[i][k]+P[k][j])

n=input()
m=input()
INF=1e10
C=[[INF]*n for i in range(n)]
for i in range(n):
    C[i][i]=0
for i in range(m):
    a1,b1,c1,d1=map(int,raw_input().split(","))
    C[a1-1][b1-1]=c1
    C[b1-1][a1-1]=d1
floyd(C,n)
x1,x2,y1,y2=map(int,raw_input().split(","))
print y1-y2-C[x1-1][x2-1]-C[x2-1][x1-1]

Submission status: Accepted

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
        costs[cur_node] = cur_cost
        #print costs
        
        for i in xrange(node_num):
            if not visited[i]:
                heapq.heappush(pq,[graph[cur_node][i] + costs[cur_node],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: Accepted

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
        costs[cur_node] = cur_cost
        #print costs
        
        for i in xrange(node_num):
            if not visited[i]:
                heapq.heappush(pq,[graph[cur_node][i] + costs[cur_node],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(","))
cost = dijkstra(home,shop,graph) + dijkstra(shop,home,graph)
print reward - price - cost

Submission status: Accepted

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
    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
        visited[cur_node] = True
        costs[cur_node] = cur_cost
        for i in xrange(node_num):
            if not visited[i]:
                heapq.heappush(pq,[graph[cur_node][i] + costs[cur_node],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[a][b] = c
    graph[b][a] = d
home,shop,reward,price = map(int,raw_input().split(","))
cost = dijkstra(home,shop,graph) + dijkstra(shop,home,graph)
print reward - price - cost

Submission status: Accepted

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
    heapq.heappush(pq, [0,start])
    while not len(pq) == 0:

        cur_cost,cur_node = heapq.heappop(pq)
        if visited[cur_node]:
            continue
        visited[cur_node] = True
        costs[cur_node] = cur_cost
        for i in xrange(node_num):
            if not visited[i]:
                heapq.heappush(pq,[graph[cur_node][i] + costs[cur_node],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[a][b] = c
    graph[b][a] = d
home,shop,reward,price = map(int,raw_input().split(","))
cost = dijkstra(home,shop,graph) + dijkstra(shop,home,graph)
print reward - price - cost

Submission status: Accepted

Solution code:
class Highway(object):
    def __init__(self, a = 0, b = 0, c = 0, d = 0):
        if isinstance(a,list):
            d = a[3]
            c = a[2]
            b = a[1]
            a = a[0]
        self.root = [int(a),int(b)]
        self.atob = int(c)
        self.btoa = int(d)

    def getRoot(self):
        return self.root

    def hasTown(self, n):
        if (self.root[0] is n) or (self.root[1] is n):
            return True
        else:
            return False

    def getNextAndCost(self, n):
        if self.root[0] is n:
            return [self.root[1], self.atob]
        elif self.root[1] is n:
            return [self.root[0], self.btoa]
        else:
            return [-1,-1]


class Town(object):
    def __init__(self, town = -1, highwayList = []):
        self.town = town
        self.path = []
        self.cost = -1
        self.done = False

        for n in highwayList:
            if n.hasTown(town):
                self.path.append(n.getNextAndCost(town))

    def __str__(self):
        text = "Town: " + str(self.town) + "\nCost: " + str(self.cost) + "\n"
        
        for i in self.path:
            text += "\tNext: " + str(i[0]) + " | Cost: " + str(i[1]) + "\n" 
        return  text

    def getTown(self):
        return self.town

    def getPath(self):
        return self.path

    def hasDone(self):
        return self.done

    def reset(self):
        self.cost = -1
        self.done = False

    def setCost(self, cost):
        self.cost = cost

    def getCost(self):
        return self.cost

    def decision(self):
        self.done = True

        
class Towns(object):
    def __init__(self, townN = 0, highway = []):
        self.townList = []
        for i in xrange(townN):
            self.townList.append(Town(i+1, highwayList))
        
    def __str__(self):
        text = ""
        for town in self.townList:
            text += str(town) 
        return text

    def getTown(self, n):
        for town in self.townList:
            if town.getTown() is n:
                return town
        return Town()

    def resetAll(self):
        for t in self.townList:
            t.reset()

    def trace(self, start, goal):
        self.resetAll()
        self.getTown(start).setCost(0)
        while True:
            doneTown = Town()
            for town in self.townList:
                if town.hasDone() or town.getCost() < 0:
                    continue
                if doneTown.getTown() == -1 or town.getCost() < doneTown.getCost():
                    doneTown = town

            if doneTown.getTown() == -1:
                break
            
            doneTown.decision()
            for p in doneTown.getPath():
                to = p[0]

                cost = doneTown.getCost() + p[1]
                if self.getTown(to).getCost() < 0 or cost < self.getTown(to).getCost():
                    self.getTown(to).setCost(cost)

        return self.getTown(goal).getCost()

townN = int(raw_input())
highwayN = int(raw_input())
highwayList = []

for i in xrange(highwayN):
    tmp = [int(h) for h in raw_input().split(",")]
    highwayList.append(Highway(tmp))

carpenter = [int(n) for n in raw_input().split(",")]

towns = Towns(townN,highwayList)

cost = towns.trace(carpenter[0], carpenter[1]) + towns.trace(carpenter[1], carpenter[0])

print carpenter[2] - carpenter[3] -cost

Submission status: Accepted

Solution code:

machi_number = input()
road_number = input()
mapp = [[10000 for j in range(machi_number)] for i in range(machi_number)]


for i in range(road_number):
	a,b,c,d =map(int, raw_input().split(","))
	aa = a-1
	bb = b-1
	mapp[aa][bb] = c
	mapp[bb][aa] = d
for i in range(machi_number):
	mapp[i][i] = 0

for k in range(machi_number):
	for i in range(machi_number):
		for j in range(machi_number):
			if mapp[i][j] > (mapp[i][k] + mapp[k][j]):
				mapp[i][j] = mapp[i][k] + mapp[k][j]

x1,x2,y1,y2 = map(int, raw_input().split(","))
print y1 - y2 - mapp[x1-1][x2-1] - mapp[x2-1][x1-1]

Submission status: Accepted

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] > -1:
				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 = [[-1]*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:
n = int(input())
m = int(input())
K = [[float('inf') for i in range(n)] for j in range(n)]
#print(K)
for i in range(m):
    a,b,c,d = map(int,input().split(','))
    #print(a,b,c,d)
    K[a-1][b-1] = c
    K[b-1][a-1] = d
for k in range(n):
    for i in range(n):
        for j in range(n):
            if K[i][j] > K[i][k]+K[k][j]:
                K[i][j] = K[i][k]+K[k][j]
    #print(K)
s,g,V,P = map(int,input().split(','))
print(V-P-K[s-1][g-1]-K[g-1][s-1])

Submission status: Accepted

Solution code:
n = int(input())
m = int(input())
inf = 1001001001
route = [[inf for _ in range(n)] for __ in range(n)]
for _ in range(m):
    a, b, c, d = map(int, input().split(','))
    route[a-1][b-1] = c
    route[b-1][a-1] = d
s, g, V, P = map(int, input().split(','))
for k in range(n):
    for i in range(n):
        for j in range(n):
            if route[i][j] > route[i][k] + route[k][j]:
                route[i][j] = route[i][k] + route[k][j]
print(int(V - P - route[s-1][g-1] - route[g-1][s-1]))

Submission status: Accepted

Solution code:
n= int(input())
m=int(input())
inf=1001001001
data =[[inf]*n for i in range(n)]

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if data[i][j]>data[i][k]+data[k][j]:
                data[i][j]= data[i][k]+data[k][j]
                
print(V-P-data[s-1][g-1]-data[g-1][s-1])

Submission status: Accepted

Solution code:
inf=200000
n=int(input())
m=int(input())
adj=[[inf]*(n+1) for i in range(n+1)]
for i in range(m):
  a,b,c,d=map(int,input().split(sep=','))
  adj[a][b]=c
  adj[b][a]=d
s,g,v,p=map(int,input().split(sep=','))
for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])
ans=v-p
ans-=adj[s][g]
ans-=adj[g][s]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    M = int(input())
    dist = [[INF]*N for _ in range(N)]
    for _ in range(M):
        a,b,c,d = map(int,input().split(','))
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = d
    s,g,v,p = map(int,input().split(','))
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][k] + dist[k][j],dist[i][j])
    s -= 1
    g -= 1
    ans = v - dist[s][g] - dist[g][s] - p
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def solve():
    N = int(input())
    M = int(input())
    G = [[] for i in range(N)]
    for i in range(M):
        a, b, c, d = map(int, input().split(","))
        G[a-1].append((b-1, c))
        G[b-1].append((a-1, d))
    s, g, V, P = map(int, input().split(","))
    INF = 10**18
    def calc(s, g):
        dist = [INF]*N
        dist[s] = 0
        que = [(0, s)]
        while que:
            cost, v = heappop(que)
            if dist[v] < cost:
                continue
            for w, d in G[v]:
                if cost + d < dist[w]:
                    dist[w] = cost + d
                    heappush(que, (cost + d, w))
        return dist[g]
    s -= 1; g -= 1
    print(max(0, V - (calc(s, g) + calc(g, s)) - P))
solve()

Submission status: Accepted

Solution code:
n = int(input())
m = int(input())
Map = [[1001]*n for _ in range(n)]
for _ in range(m):
    a,b,c,d = map(int,input().split(","))
    Map[a-1][b-1] = c
    Map[b-1][a-1] = d
s,g,V,P = map(int,input().split(","))


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

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

Submission status: Accepted

Solution code:
'''
大工の褒美
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117&lang=jp
'''

town_num = int(input()) # (<= 20)
road_num = int(input()) # (<= 100)

costs = [[100000]*town_num for _ in range(town_num)]

# [a, b, c, d] a から b まで c, 逆は d の交通費がかかる
for a, b, c, d in [list(map(int, input().split(','))) for _ in range(road_num)]:
    costs[a-1][b-1] = c
    costs[b-1][a-1] = d

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

# Floyd Warshall
for k in range(town_num):
    for i in range(town_num):
        for j in range(town_num):
            if costs[i][j] > costs[i][k] + costs[k][j]:
                costs[i][j] = costs[i][k] + costs[k][j]

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

Submission status: Accepted

Solution code:
n = int(input())
m = int(input())
cost = []
for i in range(n):
    t = [float('inf')]*n
    t[i] = 0
    cost.append(t)
for i in range(m):
    s = input()
    s += ','
    L = []
    z = ''
    for j in range(len(s)):
        if s[j] != ',':
            z += s[j]
        else:
            L.append(int(z))
            z = ''
    a,b,c,d = L[0],L[1],L[2],L[3]
    cost[a-1][b-1] = c
    cost[b-1][a-1] = d
for k in range(n):
    for i in range(n):
        for j in range(n):
            if cost[i][j] > cost[i][k]+cost[k][j]:
                cost[i][j] = cost[i][k]+cost[k][j]
s = input()
s += ','
L = []
z = ''
for j in range(len(s)):
    if s[j] != ',':
        z += s[j]
    else:
        L.append(int(z))
        z = ''
s,g,v,p = L[0],L[1],L[2],L[3]
print(v-p-cost[s-1][g-1]-cost[g-1][s-1])

Submission status: Accepted

Solution code:
n=int(input())
m=int(input())
l=[]
for i in range(m):
  l1=list(map(int,input().split(",")))
  l.append(l1)
s,g,v,p=map(int,input().split(","))
listl=[[100000 for i in range(n+1)] for i in range(n+1)]
for i in l:
  listl[i[0]][i[1]]=i[2]
  listl[i[1]][i[0]]=i[3]
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      if listl[j][k]>listl[j][i]+listl[i][k]:
        listl[j][k]=listl[j][i]+listl[i][k]
print(v-p-(listl[s][g]+listl[g][s]))

Submission status: Accepted

Solution code:
n = int(input())
m = int(input())
K = [[10**9 for one in range(32)] for two in range(32)]
for three in range(m):
    a,b,c,d = map(int,input().split(","))
    K[a][b] = c
    K[b][a] = d

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

s,g,V,P = map(int,input().split(","))
print(V-P-K[s][g]-K[g][s])

Submission status: Accepted

Solution code:
n=int(input())
cost=[[float('inf')]*n for _ in range(n)]
m=int(input())
for _ in range(m):
    a,b,c,d=map(int,input().split(','))
    cost[a-1][b-1]=c
    cost[b-1][a-1]=d
s,g,V,P=map(int,input().split(','))

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

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

Submission status: Accepted

Solution code:
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:
n = int(input())
m = int(input())
mat = [[float("inf")]*n for _ in [0]*n]
for a,b,c,d in((map(int, input().split(","))) for _ in [0]*m):
    mat[a-1][b-1] = c
    mat[b-1][a-1] = d
s,g,v,p = map(int, input().split(","))
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
print(v-p-mat[s-1][g-1]-mat[g-1][s-1])

Submission status: Accepted

Solution code:
N = int(input().strip())
M = int(input().strip())
Inf = 1001001001
K = [[Inf for j in range(N)] for i in range(N)]
for _ in range(M):
    a,b,c,d = map(int,input().strip().split(","))
    K[a-1][b-1] = c
    K[b-1][a-1] = d
S,G,V,P = map(int,input().strip().split(","))
for k in range(N):
    for i in range(N):
        for j in range(N):
            if K[i][j] > K[i][k] + K[k][j]:
                K[i][j] = K[i][k] + K[k][j]
R = V - P - K[S-1][G-1] - K[G-1][S-1]
print(R)

Submission status: Accepted

Solution code:
import sys
n = int(input())
m = int(input())
cost = [[float("inf")] * n for _ in range(n)]
for _ in range(m):
    a, b, c, d = map(int, sys.stdin.readline().split(","))
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = d
s, g, V, P = map(int, sys.stdin.readline().split(","))

for k in range(n):
    for i in range(n):
        c_ik = cost[i][k]
        for j, (c_kj, c_ij) in enumerate(zip(cost[k], cost[i])):
            temp = c_ik + c_kj
            if c_ij > temp:
                cost[i][j] = temp

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
def solve(graph,start,goal,numnodes):
    que = []
    heappush(que,(0,start-1))
    mindists = [float("inf")]*numnodes
    while que:
        ccost,cnode = heappop(que)
        if mindists[cnode] < ccost: continue
        for nnode,mcost in graph[cnode]:
            tcost = ccost+mcost
            if mindists[nnode] > tcost:
                mindists[nnode] = tcost
                heappush(que,(tcost,nnode))
    return mindists[goal-1]
n = int(input())
m = int(input())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b,c,d = map(int,input().split(","))
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,d))
s,g,V,P = map(int, input().split(","))
V -= solve(graph,s,g,n)
V -= P
V -= solve(graph,g,s,n)
print(V)

Submission status: Runtime Error

Solution code:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117

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: Runtime Error

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__':
    l_dic = {}
    p_dic = {}
    for line in open('s.txt').readlines():
        n1, n2, p1, p2 = map(int, line.rstrip().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: Runtime Error

Solution code:
import numpy as np

n = int(input())
m = int(input())
road = np.full((n, n), np.inf)
for i in range(m):
    r_in = list(map(int, input().split(",")))
    road[r_in[0]-1, r_in[1]-1] = r_in[2]
    road[r_in[1]-1, r_in[0]-1] = r_in[3]
s, g, v, p = map(int, input().split(","))

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                road[i, j] = 0
            else:
                road[i, j] = min(road[i, j], road[i, k] + road[k, j])

reward = int(v - road[s-1, g-1] - road[g-1, s-1] - p)
print(reward)