Problem:


 JOI 国の買い物事情(Shopping in JOI Kingdom) 

JOI 国にはN 個の町があり，それらの間はM 本の双方向に通行可能な道路で結ばれている．K 個の町にはショッピングモールがあり，国民は道路を通ってそれらの町のいずれかに行き買い物をする．

家の場所によっては，買い物に行くために長い距離を移動する必要があり，それは非常に不便である．国王はこの実情を把握するため，ショッピングモールのある町までの最短距離が家の場所によってどれだけ長くなりうるのかを調べることにした．家は道路の途中に建てられることもあるので(入力例1 の説明を参照)，この調査は非常に大変である．そこで国王は，優秀なプログラマーであるあなたに，調査を行うプログラムの作成を依頼した．

課題

道路の情報とショッピングモールのある町の情報が与えられるとき，ショッピングモールのある町からもっとも遠い道路上の点(端点も含む) までの距離を求めるプログラムを作成せよ．町の中を移動するのにかかる距離は無視してよい．

制限

2 ≤ N ≤ 3000     JOI 国の町の個数

1 ≤ M ≤ 100000 = 105     JOI 国の道路の本数

1 ≤ K ≤ N     ショッピングモールがある町の個数

1 ≤ li ≤ 1000     i 番目の道路の長さ

入力

標準入力から以下の入力を読み込め．

 1 行目には整数N, M, K が空白区切りで書かれている．N はJOI 国の町の個数を，M はJOI 国の道路の本数を，i>K はショッピングモールがある町の個数をそれぞれ表す．町には1, 2, ...,  N の番号がつけられている．

 続くM 行は道路の情報を表す．i + 1 行目(1 ≤ i ≤ M) には整数ai, bi, li (1 ≤ ai ≤ N, 1 ≤ bi ≤ N, 1 ≤ li ≤ 1000) が空白区切りで書かれている．これは，i 本目の道路が町ai と町bi を結んでおり，長さがli であることを表す．道路の両端が同じ町であることはない．また，任意の2 つの町p, q に対し，pとq を結ぶ道路は2 本以上存在しない．どの町からどの町へもいくつかの道路をたどって行くことができる．

続くK 行はショッピングモールの情報を表す．i+M+1 行目(1 ≤ i ≤ K) には1 つの整数si (1 ≤ si ≤ N)が書かれている．これは町si にショッピングモールがあることを表す．s1, ...,  sK の中に同じ値が2
回以上現れることはない．

出力

標準出力に，ショッピングモールのある町までの最短距離の最大値の小数点以下を四捨五入した整数1
つを出力せよ．

採点基準

採点用データのうち，配点の40% 分については，K = 1 を満たす．

入出力の例

入力例1
  

3 3 1
1 2 1
2 3 1
3 1 1
1

出力例1
  

2

入力例1 は次のような町を表す．道路の長さはすべて1 である．ショッピングモールは町1 にしかない．

ショッピングモールのある町までもっとも遠い点は，町2 と町3 を結ぶ道路上の，町2 から距離0.5 の位置にある点であり，ショッピングモールのある町までの距離は1.5 である．よって，それを四捨五入した値である2 を出力する．

入力例2
  

4 5 2
1 2 4
1 3 1
2 3 2
2 4 2
3 4 1
2
4

出力例2
  

3

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 3 1
1 2 1
2 3 1
3 1 1
1


Sample output:
2

Submission status: Wrong Answer

Solution code:
import heapq

def dijkstra(s,g,c):
    visited=[0]*(n+m)
    d=[float('inf')]*(n+m)
    d[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        visited[u]=2
        if d[u]<t:
            continue
        for v in g[u]:
            if visited[v]!= 2:
                if d[u]+c[u][v]<d[v]:
                    d[v]=d[u]+c[u][v]
                    visited[v]=1
                    heapq.heappush(pq,[d[v],v])
    return d

n,m,k=map(int,raw_input().split())
g=[[] for _ in xrange(n+m)]
cost=[[0]*(n+m) for _ in xrange(n+m)]

for i in xrange(m):
    a,b,l=map(int,raw_input().split())
    a-=1;b-=1;c=n+i
    g[a].append(c)
    g[c].append(a)
    g[b].append(c)
    g[c].append(b)
    cost[a][c]=l/2.0
    cost[b][c]=l/2.0
    cost[c][a]=cost[a][c]
    cost[c][b]=cost[b][c]

shop=[int(raw_input()) for _ in xrange(k)]
ans=float('inf')
for i in xrange(k):
    pq=[]
    dis=dijkstra(shop[i],g,cost)
    ans=min(ans,max(dis))

print(int(round(ans)))

Submission status: Accepted

Solution code:
import heapq

n,m,K=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
cost=[[10**5]*n for _ in xrange(n)]

for i in xrange(m):
    a,b,l=map(int,raw_input().split())
    a-=1;b-=1
    g[a].append(b)
    g[b].append(a)
    cost[a][b]=l
    cost[b][a]=l

pq=[]
d=[float('inf')]*n
for i in xrange(K):
    c=int(raw_input())-1
    heapq.heappush(pq,[0,c])
    d[c]=0
while len(pq)!=0:
    t,u=heapq.heappop(pq)
    if d[u]<t:
        continue
    for v in g[u]:
        if d[u]+cost[u][v]<d[v]:
            d[v]=d[u]+cost[u][v]
            heapq.heappush(pq,[d[v],v])

ans=0
for i in xrange(n):
    for j in g[i]:
        ans=max(ans,(1+d[i]+d[j]+cost[i][j])/2)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop as pop
from heapq import heappush as push

INF = 10 ** 18

class edge:
  def __init__(self, to, cost):
    self.to = to
    self.cost = cost

#V, E, r = map(int,input().split())
N, M, K = map(int,input().split())

G = [[] for i in range(N)]
#G[i]...頂点iからの辺list、(行き先、コスト)

d = [INF for i in range(N)]
#d[i]...スタートからみた頂点iまでの最短距離

def dijkstra(lst):
  que = []
  for s in lst:
    d[s] = 0
    push(que, (0,s))

  while len(que):
    p = pop(que)
    v = p[1]
    if (d[v] < p[0]):
      continue
    for i in range(len(G[v])):
      e = G[v][i]
      if d[e.to] > d[v] + e.cost:
        d[e.to] = d[v] + e.cost
        push(que, (d[e.to], e.to))

for i in range(M):
  s, t, c = map(int,input().split())
  s -= 1
  t -= 1
  G[s].append(edge(t,c))
  G[t].append(edge(s,c))


lst =  [int(input()) - 1 for i in range(K)]
dijkstra(lst)

anss = []
append = anss.append

for i in range(N):
  for e in G[i]:
    x = d[i] + d[e.to] + e.cost
    if x % 2:
      append(x // 2 + 1)
    else:
      append(x // 2)

print(max(anss))

Submission status: Accepted

Solution code:
from heapq import heappop as pop
from heapq import heappush as push

def solve():
  
  INF = 10 ** 18
  
  class edge:
    def __init__(self, to, cost):
      self.to = to
      self.cost = cost
  
  N, M, K = map(int,input().split())
  
  G = [[] for i in range(N)]
  #G[i]...頂点iからの辺list、(行き先、コスト)
  
  d = [INF for i in range(N)]
  #d[i]...スタートからみた頂点iまでの最短距離
  
  def dijkstra(lst):
    que = []
    for s in lst:
      d[s] = 0
      push(que, (0,s))
  
    while len(que):
      p = pop(que)
      v = p[1]
      if (d[v] < p[0]):
        continue
      for i in range(len(G[v])):
        e = G[v][i]
        if d[e.to] > d[v] + e.cost:
          d[e.to] = d[v] + e.cost
          push(que, (d[e.to], e.to))
  
  for i in range(M):
    s, t, c = map(int,input().split())
    s -= 1
    t -= 1
    G[s].append(edge(t,c))
    G[t].append(edge(s,c))
  
  
  lst =  [int(input()) - 1 for i in range(K)]
  dijkstra(lst)
  
  anss = []
  append = anss.append
  
  for i in range(N):
    for e in G[i]:
      x = d[i] + d[e.to] + e.cost
      if x % 2:
        append(x // 2 + 1)
      else:
        append(x // 2)
  
  print(max(anss))

solve()

Submission status: Accepted

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

"""
import sys
from heapq import heappush, heappop
from itertools import combinations


def dijkstra(adj, s):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(adj)
    d = [float('inf')] * len(adj)
    d[s] = 0
    pq = []
    heappush(pq, (0, s))
    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue
        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d


def solve(adj, malls, n):
    distance = dijkstra(adj, malls[0])
    ans = [max([(d + j[1] + distance[j[0]])/2 for j in adj[n]]) for n, d in enumerate(distance[1:], start=1)]
    return int(max(ans) + 0.5) 


def main(args):
    n, m, k = map(int, input().split())
    adj = [[] for _ in range(n+1)]
    for _ in range(m):
        f,t, c = map(int, input().split())
        adj[f].append((t, c))
        adj[t].append((f, c))

    malls = [int(input()) for _ in range(k)]
    for f, t in combinations(malls, 2):
        adj[f].append((t, 0))
        adj[t].append((f, 0))
    ans = solve(adj, malls, n)
    print(ans)


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