Problem:


Water Pipe Construction

21XX 年，ついに人類は火星への移住計画を開始させた．火星への移住第一陣に選抜されたあなたは，火星行政中央局（the Administrative Center of Mars）に配属され，火星で起こる様々な問題に対処している．行政中央局の目下の最大の問題は自立した需要供給サイクルの確保である．月からの援助物資が届くまでには数ヶ月単位の時間がかかるため，基本的には火星内の需要は火星内で解決する必要がある．それに加えて，循環システムを確立するまでは資源を極力節約することが求められる．

行政中央局は極地にある氷の採掘を開始した．太陽光でこれを溶かし，水として個々の基地に供給することが最終目標である．最初の段階として，水源のある基地から2つの主要基地までの導水管を敷設することにした．また，現時点ではいくつかの基地とそれらを結ぶ道路以外には開拓されておらず，未開拓のところに導水管を敷設するには多大なるコストと燃料を要するため，道路に沿って導水管を敷設することにした．さらに，技術上の制約のため，彼らの導水管は常に一方向だけに水が流れる．

あなたの仕事は，これらの条件のもとで，導水管の敷設にかかるコストを最小にするプログラムを作成することである．

Input

入力は複数のデータセットから構成される．

データセットの最初の行は 5 つの整数からなる．これらは順に，火星に存在する基地の数 n (3 <= n <= 100)，基地を結ぶ道路の数 m (2 <= m <= 1000)，水源となる基地の番号 s， 導水管の目的地となる 2 つの主要基地の番号 g1，g2 を表す．基地の番号は 1 から n までの整数で表される．s，g1，g2 は互いに異なる．

続く m 行には，導水管を敷設可能な道路の情報が与えられる．各行はある 2 つの基地間における道路の情報を表しており，3 つの整数 b1，b2，c (1 <= c <= 1000) からなる．ここに b1，b2 は道路の始端および終端の基地の番号を表し，これらは互いに異なる．c は基地 b1 から基地 b2 に向かう導水管を敷設するためにかかるコストである．

全てのデータセットについて，水源から目的地まで水を供給する経路は常に存在すると仮定してよい．また，ある 2 つの基地間には高々 1 つの道路しか存在しないことから，コストの情報はそれぞれの方向について高々 1 回しか与えられない．

入力の終了はスペース文字で区切られた 5 つのゼロが含まれる行で表される．

Output

それぞれのデータセットに対して，導水管を敷設するコストの最小値を 1 行に出力せよ．

Sample Input

4 5 1 3 4
1 2 5
2 3 5
2 4 5
1 3 8
1 4 8
0 0 0 0 0

Output for the Sample Input

15



Sample input:
4 5 1 3 4
1 2 5
2 3 5
2 4 5
1 3 8
1 4 8
0 0 0 0 0


Sample output:
15

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
from operator import add

SENTINEL = 100000
while True:
    n, m, s, g1, g2 = map(int, input().split())
    s -= 1
    g1 -= 1
    g2 -= 1
    if not n:
        break
    pipes = [set() for _ in range(n)]
    rpipes = [set() for _ in range(n)]
    for _ in range(m):
        b1, b2, c = map(int, input().split())
        b1 -= 1
        b2 -= 1
        pipes[b1].add((c, b2))
        rpipes[b2].add((c, b1))

    dists = [[SENTINEL] * n for _ in range(2)]

    for i in (0, 1):
        g = (g1, g2)[i]
        dist = dists[i]
        dist[g] = 0
        queue = list(rpipes[g])
        heapify(queue)
        while queue:
            total_cost, base = heappop(queue)
            if dist[base] < SENTINEL:
                continue
            dist[base] = total_cost
            for next_cost, next_base in rpipes[base]:
                if dist[next_base] == SENTINEL:
                    heappush(queue, (total_cost + next_cost, next_base))

    dists = list(map(add, *dists))

    current_best = dists[s]
    queue = list(pipes[s])
    heapify(queue)
    visited = {s}
    while queue:
        total_cost, base = heappop(queue)
        if base in visited:
            continue
        visited.add(base)
        current_best = min(current_best, total_cost + dists[base])
        for next_cost, next_base in pipes[base]:
            if next_base not in visited:
                next_whole_cost = total_cost + next_cost + dists[next_base]
                if current_best > next_whole_cost:
                    heappush(queue, (total_cost + next_cost, next_base))

    print(current_best)

Submission status: Wrong Answer

Solution code:
while True:
    N, M, s, g1, g2 = map(int, input().split())
    if N == M == s == g1 == g2 == 0:
        break
    s, g1, g2 = s - 1, g1 - 1, g2 - 1
    INF = 10 ** 5
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        s, t, c = map(int, input().split())
        s, t = s - 1, t - 1
        D[s][t] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    print(min(D[s][i] + min(D[i][g1] + D[i][g2], D[i][g1] + D[g1][g2], D[i][g2] + D[g2][g1]) for i in range(N)))

Submission status: Wrong Answer

Solution code:
while True:
    N, M, s, g1, g2 = map(int, input().split())
    if N == M == s == g1 == g2 == 0:
        break
    s, g1, g2 = s - 1, g1 - 1, g2 - 1
    INF = 10 ** 8
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        s, t, c = map(int, input().split())
        s, t = s - 1, t - 1
        D[s][t] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    print(min(D[s][i] + min(D[i][g1] + D[i][g2], D[i][g1] + D[g1][g2], D[i][g2] + D[g2][g1]) for i in range(N)))

Submission status: Wrong Answer

Solution code:
while True:
    N, M, s, g1, g2 = map(int, input().split())
    if N == M == s == g1 == g2 == 0:
        break
    s, g1, g2 = s - 1, g1 - 1, g2 - 1
    INF = 10 ** 8
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        s, t, c = map(int, input().split())
        s, t = s - 1, t - 1
        D[s][t] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    print(min(D[s][i] + D[i][g1] + D[i][g2] for i in range(N)))

Submission status: Wrong Answer

Solution code:
while True:
    N, M, s, g1, g2 = map(int, input().split())
    if N == M == s == g1 == g2 == 0:
        break
    s, g1, g2 = s - 1, g1 - 1, g2 - 1
    INF = 1 << 30
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        s, t, c = map(int, input().split())
        s, t = s - 1, t - 1
        D[s][t] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    print(min(D[s][i] + D[i][g1] + D[i][g2] for i in range(N)))

Submission status: Wrong Answer

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
while True:
    N, M, s, g1, g2 = map(int, input().split())
    if N == M == s == g1 == g2 == 0:
        break
    s, g1, g2 = s - 1, g1 - 1, g2 - 1
    INF = 1 << 30
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        s, t, c = map(int, input().split())
        s, t = s - 1, t - 1
        D[s][t] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    print(min(D[s][i] + D[i][g1] + D[i][g2] for i in range(N)))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []


    while True:
        n,m,s,g1,g2 = LI()
        if n == 0:
            break
        e = collections.defaultdict(list)
        for _ in range(m):
            a,b,c = LI()
            e[a].append((b,c))
            e[b].append((a,c))

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for uv, ud in e[u]:
                    if v[uv]:
                        continue
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return d

        sd = search(s)
        r = inf
        for i in range(1,n+1):
            td = search(i)
            tr = sd[i] + td[g1] + td[g2]
            if r > tr:
                r = tr

        rr.append(r)

    return '\n'.join(map(str, rr))



print(main())

Submission status: Wrong Answer

Solution code:
from itertools import product
INF = 1 << 30
while True:
    n, m, s, g1, g2 = map(int, raw_input().split())
    if n | m | s | g1 | g2 == 0:
        break
    G = [[INF] * (n + 1) for _ in xrange(n + 1)]
    for _ in xrange(m):
        b1, b2, c = map(int, raw_input().split())
        G[b1][b2] = c
    for k, i, j in product(xrange(n), repeat = 3):
        G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    print min(G[s][m] + G[m][g1] + G[m][g2] for m in xrange(n))

Submission status: Wrong Answer

Solution code:
from itertools import product
INF = 1 << 30
while True:
    n, m, s, g1, g2 = map(int, raw_input().split())
    if n | m | s | g1 | g2 == 0:
        break
    G = [[INF] * (n + 1) for _ in xrange(n + 1)]
    for _ in xrange(m):
        b1, b2, c = map(int, raw_input().split())
        G[b1][b2] = c
    for k, i, j in product(xrange(n + 1), repeat = 3):
        G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    print min(G[s][i] + G[i][g1] + G[i][g2] for i in xrange(n + 1))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
from operator import add

SENTINEL = 100000
while True:
    n, m, s, g1, g2 = map(int, input().split())
    s -= 1
    g1 -= 1
    g2 -= 1
    if not n:
        break
    pipes = [set() for _ in range(n)]
    rpipes = [set() for _ in range(n)]
    for _ in range(m):
        b1, b2, c = map(int, input().split())
        b1 -= 1
        b2 -= 1
        pipes[b1].add((c, b2))
        rpipes[b2].add((c, b1))

    dists = [[SENTINEL] * n for _ in range(2)]

    for i in (0, 1):
        g = (g1, g2)[i]
        dist = dists[i]
        dist[g] = 0
        queue = list(rpipes[g])
        heapify(queue)
        while queue:
            total_cost, base = heappop(queue)
            if dist[base] < SENTINEL:
                continue
            dist[base] = total_cost
            for next_cost, next_base in rpipes[base]:
                if dist[next_base] == SENTINEL:
                    heappush(queue, (total_cost + next_cost, next_base))

    dists = list(map(add, *dists))

    current_best = dists[s]
    queue = list(pipes[s])
    heapify(queue)
    visited = {s}
    while queue:
        total_cost, base = heappop(queue)
        if base in visited:
            continue
        visited.add(base)
        current_best = min(current_best, total_cost + dists[base])
        for next_cost, next_base in pipes[base]:
            if next_base not in visited:
                heappush(queue, (total_cost + next_cost, next_base))

    print(current_best)

Submission status: Accepted

Solution code:
import sys

def warshall(n, matrix):
  for i in xrange(n):
    matrix[i][i] = 0
  for i in xrange(n):
    for j in xrange(n):
      for k in xrange(n):
        matrix[j][k] = min(matrix[j][k], matrix[j][i]+matrix[i][k])
  return matrix

while True:
  n,m,s,g1,g2 = map(int, raw_input().split())
  if n==m==s==g1==g2==0:
    break
  matrix = [[10**10] * n for i in xrange(n)]
  for i in xrange(m):
    b1,b2,c = map(int, raw_input().split())
    matrix[b1-1][b2-1] = c
  costs = warshall(n, matrix)
  mincost = 10**10
  for i in xrange(n):
    mincost = min(mincost, costs[s-1][i]+costs[i][g1-1]+costs[i][g2-1])
  print mincost

Submission status: Accepted

Solution code:
while True:
    N, M, s, g1, g2 = map(int, input().split())
    if N == M == s == g1 == g2 == 0:
        break
    s, g1, g2 = s - 1, g1 - 1, g2 - 1
    INF = 10 ** 5
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        b1, b2, c = map(int, input().split())
        b1, b2 = b1 - 1, b2 - 1
        D[b1][b2] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    print(min(D[s][i] + D[i][g1] + D[i][g2] for i in range(N)))

Submission status: Accepted

Solution code:
while True:
    N, M, s, g1, g2 = map(int, input().split())
    if N == M == s == g1 == g2 == 0:
        break
    s, g1, g2 = s - 1, g1 - 1, g2 - 1
    INF = 10 ** 5
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        b1, b2, c = map(int, input().split())
        b1, b2 = b1 - 1, b2 - 1
        D[b1][b2] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if D[i][j] > D[i][k] + D[k][j]:
                    D[i][j] = D[i][k] + D[k][j]
    print(min(D[s][i] + D[i][g1] + D[i][g2] for i in range(N)))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []


    while True:
        n,m,s,g1,g2 = LI()
        if n == 0:
            break
        e = collections.defaultdict(list)
        for _ in range(m):
            a,b,c = LI()
            e[a].append((b,c))

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for uv, ud in e[u]:
                    if v[uv]:
                        continue
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return d

        sd = search(s)
        r = inf
        for i in range(1,n+1):
            td = search(i)
            tr = sd[i] + td[g1] + td[g2]
            if r > tr:
                r = tr

        rr.append(r)

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

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

while True:
    n,m,s,g1,g2=map(int,raw_input().split())
    if n==0:break
    s-=1
    g1-=1
    g2-=1
    INF=1e10
    L=[[INF]*n for i in range(n)]
    for i in range(n):
        L[i][i]=0
    for i in range(m):
        b1,b2,c=map(int,raw_input().split())
        b1-=1
        b2-=1
        L[b1][b2]=c
    floyd(n,L)
    ans=INF
    for i in range(n):
        ans=min(ans,L[s][i]+L[i][g1]+L[i][g2])
    print ans

Submission status: Accepted

Solution code:
from itertools import product
INF = 1 << 30
while True:
    n, m, s, g1, g2 = map(int, raw_input().split())
    if n | m | s | g1 | g2 == 0:
        break
    G = [[INF] * (n + 1) for _ in xrange(n + 1)]
    for i in xrange(n + 1):
        G[i][i] = 0
    for _ in xrange(m):
        b1, b2, c = map(int, raw_input().split())
        G[b1][b2] = c
    for k, i, j in product(xrange(n + 1), repeat = 3):
        G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    print min(G[s][i] + G[i][g1] + G[i][g2] for i in xrange(n + 1))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def cal(x,y,a):
    return (x+y*W)*4 + a

def uncal(val):
    a = val%4
    vxy = val//4
    x,y = vxy%W, vxy//W
    return x,y,a

def dijkstra(lines,N,s):
    weight = [INF]*N
    weight[s] = 0
    def search(s,w_0,q,weight):
        for t,w in lines[s]:
            w += w_0
            if weight[t] > w:
                heapq.heappush(q,[w,t])
                weight[t] = w
    q = [[0,s]]
    heapq.heapify(q)
    while q:
        w,n = heapq.heappop(q)
        search(n,w,q,weight)
    return weight



while True:
    N,M,s,g1,g2 = inpl()
    if N == 0 and M == 0:
        break
    else:
        lines1 = defaultdict(set)
        lines2 = defaultdict(set)
        for _ in range(M):
            x,y,c = inpl()
            x,y = x-1,y-1
            lines1[x].add((y,c))
            lines2[y].add((x,c))

        weights_s  = dijkstra(lines1,N,s-1)
        weights_b1 = dijkstra(lines2,N,g1-1)
        weights_b2 = dijkstra(lines2,N,g2-1)

        ans = INF
        for i in range(N):
            tmp = weights_s[i] + weights_b1[i] + weights_b2[i]
            ans = min(ans,tmp)
        print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

def dijkstra(s):
    d = [float("inf") for i in range(n)]
    d[s] = 0
    q = [(0,s)]
    while q:
        dx,x = heappop(q)
        for c,y in v[x]:
            if dx+c < d[y]:
                d[y] = dx+c
                heappush(q,(d[y],y))
    return d

while 1:
    n,m,s,g1,g2 = map(int, input().split())
    if n == m == s == g1 == g2 == 0:
        break
    s -= 1
    g1 -= 1
    g2 -= 1
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = map(int, input().split())
        v[a-1].append((c,b-1))
    d = [dijkstra(i) for i in range(n)]
    ans = d[s][g1]+d[s][g2]
    for i in range(n):
        if d[s][i]+d[i][g1]+d[i][g2] < ans:
            ans = d[s][i]+d[i][g1]+d[i][g2]
    print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def main():
  while True:
    n, m, s, g1, g2 = map(int, input().split())
    if n == 0:
      break
    s -= 1
    g1 -= 1
    g2 -= 1
  
    INF = 10 ** 20
    edges = [[] for _ in range(n)]
    for _ in range(m):
      b1, b2, c = map(int, input().split())
      b1 -= 1
      b2 -= 1
      edges[b1].append((b2, c))
  
    def dij(start):
      que = []
      heappush(que, (0, start))
      costs = [INF] * n
      costs[start] = 0
      
      while que:
        total, node = heappop(que)
        for to, dist in edges[node]:
          new_total = total + dist
          if costs[to] > new_total:
            costs[to] = new_total
            heappush(que, (new_total, to))
  
      return costs
    
    from_i = [dij(i) for i in range(n)]
    print(min([from_i[s][i] + from_i[i][g1] + from_i[i][g2] for i in range(n)]))
  
main()

Submission status: Runtime Error

Solution code:
inf = 10**10
while 1:
    n,m,s,g1,g2 = map(int,raw_input().split())
    if n == 0: break
    s,g1,g2 = s-1,g1-1,g2-1
    G = [[inf]*n for i in xrange(n)]
    for loop in xrange(m):
        b1,b2,c = map(int,raw_input().split())
        G[b1-1][b2-1] = c
    for k in xrange(n):
        for i in xrange(n):
            for j in xrange(n):
                G[i][j] = min(G[i][j], G[i][k]+G[k][j])
    ans = inf
    for i in xrange(n):
        ans = min(ans, G[s][i]+G[i][g1]+G[i][g2], G[s][i]+G[i][g1]+G[g1][g2], G[s][i]+G[i][g2]+G[g2][g1])
    print ans

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush
from operator import add

while True:
    n, m, s, g1, g2 = map(int, input().split())
    s -= 1
    g1 -= 1
    g2 -= 1
    if not n:
        break
    pipes = [set() for _ in range(n)]
    for _ in range(m):
        b1, b2, c = map(int, input().split())
        b1 -= 1
        b2 -= 1
        pipes[b1].add((c, b2))
        pipes[b2].add((c, b1))

    dists = [[None] * n for _ in range(2)]

    for i in (0, 1):
        g = (g1, g2)[i]
        dist = dists[i]
        dist[g] = 0
        queue = list(pipes[g])
        heapify(queue)
        while queue:
            total_cost, base = heappop(queue)
            if dist[base] is not None:
                continue
            dist[base] = total_cost
            for next_cost, next_base in pipes[base]:
                if dist[next_base] is None:
                    heappush(queue, (total_cost + next_cost, next_base))

    dists = list(map(add, *dists))

    current_best = dists[s]
    queue = list(pipes[s])
    heapify(queue)
    visited = {s}
    while queue:
        total_cost, base = heappop(queue)
        if base in visited:
            continue
        visited.add(base)
        current_best = min(current_best, total_cost + dists[base])
        for next_cost, next_base in pipes[base]:
            if next_base not in visited:
                next_whole_cost = total_cost + next_cost + dists[next_base]
                if current_best > next_whole_cost:
                    heappush(queue, (total_cost + next_cost, next_base))

    print(current_best)