Problem:


JOI 公園 (JOI Park)

20XX 年に IOI 国で行われるオリンピックに備え，IOI 国にある JOI 公園を整備することになった．JOI公園には N 個の広場があり，広場には 1 から N の番号がついている．広場を繋ぐ M 本の道があり，道には 1 から M の番号がついている．道 i (1 ≤ i ≤ M) は広場 Ai と広場 Bi を双方向に繋いでおり，長さは Di である．どの広場からどの広場へもいくつかの道を辿って行くことができる．

整備計画では，まず，0 以上の整数 X を選び，広場 1 からの距離が X 以下であるような広場 (広場 1 を含む) どうしをすべて相互に地下道で結ぶ．ただし，広場 i と広場 j の距離とは，広場 i から広場 j に行くときに通る道の長さの和の最小値である．整備計画では地下道の整備コストに関する整数 C が定まっている．地下道の整備にかかるコストは C &times; X である．

次に，地下道で結ばれた広場どうしを結ぶ道をすべて撤去する．道の撤去にコストはかからない．最後に，撤去されずに残った道をすべて補修する．長さ d の道を補修するためにかかるコストは d である．整備計画実施前の JOI 公園には地下道はない．JOI 公園の整備にかかるコストの和の最小値を求めよ．

課題

JOI 公園の広場の情報と，地下道の整備コストに関する整数が与えられたとき，JOI 公園の整備にかかる
コストの和の最小値を求めるプログラムを作成せよ．

入力

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

 1 行目には，整数 N, M,C が空白を区切りとして書かれている．これは，広場が N 個，道が M 本あり，地下道の整備コストに関する整数が C であることを表す．

 続く M 行のうちの i 行目 (1 ≤ i ≤ M) には，整数 Ai, Bi, Di が空白を区切りとして書かれている．これは，道 i が広場 Ai と広場 Bi を繋ぎ，長さが Di であることを表す．

出力

標準出力に，JOI 公園の整備にかかるコストの和の最小値を表す整数を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

 2 ≤ N ≤ 100 000．

 1 ≤ M ≤ 200 000．

 1 ≤ C ≤ 100 000．

 1 ≤ Ai ≤ N (1 ≤ i ≤ M)．

 1 ≤ Bi ≤ N (1 ≤ i ≤ M)．

 Ai &ne; Bi (1 ≤ i ≤ M)．

 (Ai, Bi) &ne; (Aj, Bj) および (Ai, Bi) &ne; (Bj, Aj) (1 ≤ i < j ≤ M)．

 1 ≤ Di ≤ 100 000 (1 ≤ i ≤ M)．

 与えられる入力データにおいては，どの広場からどの広場へもいくつかの道を辿ることにより行けることが保証されている．

入出力例

入力例 1 

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

出力例 1

14

この入力例では，X = 3 として，広場 1 からの距離が 3 以下であるような広場 (広場 1, 広場 2, 広場 3) どうしをすべて相互に地下道で結んだとき，整備にかかるコストの和は 2 &times; 3 + 3 + 5 = 14 となる．これが最小値である．

入力例 2

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

出力例 2

15

この入力例では，X = 0 のとき整備にかかるコストの和が最小になる．

入力例 3 

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

出力例 3

10

この入力例では，X = 5 としてすべての広場を相互に地下道で結んだとき，整備にかかるコストの和が最小になる．

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



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


Sample output:
14

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20

n, m, c = map(int, input().split())
edges = [[] for _ in range(n)]
edges_dict = {}
d_cost = 0
for _ in range(m):
  a, b, d = map(int, input().split())
  a -= 1
  b -= 1
  edges[a].append((b, d))
  edges[b].append((a, d))
  edges_dict[(a, b)] = d
  d_cost += d

dist = [INF] * n
dist[0] = 0
que = []
heappush(que, (0, 0))
while que:
  total, node = heappop(que)
  for to, d in edges[node]:
    if dist[to] > total + d:
      dist[to] = total + d
      heappush(que, (total + d, to))

removal = {}
for t, d in edges_dict.items():
  max_d = max(dist[t[0]], dist[t[1]])
  if max_d in removal:
    removal[max_d] += d
  else:
    removal[max_d] = d

ans = d_cost
for k, v in sorted(removal.items()):
  d_cost -= v
  if d_cost + k * c < ans:
    ans = d_cost + k * c

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import heapq

def dijkstra(s,g):
    color=[0]*n
    dis={}
    for i in xrange(n):
        dis[i]=float('inf')
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v,cost in g[u]:
            if color[v]!=2:
                if dis[u]+cost<dis[v]:
                    dis[v]=dis[u]+cost
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,m,c=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
totalcost=0
for i in xrange(m):
    a,b,d=map(int,raw_input().split())
    g[a-1].append([b-1,d])
    g[b-1].append([a-1,d])
    totalcost+=d

pq=[]
dis=dijkstra(0,g)
dis=sorted(dis.items(), key=lambda x:x[1])

ans=float('inf')
visited=[0]*n
for u,x in dis:
    visited[u]=1
    for v,cost in g[u]:
        if visited[v]==1:
            totalcost-=cost
    ans=min(ans,totalcost+c*x)
print ans

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s,g):
    color=[0]*n
    dis={}
    for i in xrange(n):
        dis[i]=float('inf')
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v,cost in g[u]:
            if color[v]!=2:
                if dis[u]+cost<dis[v]:
                    dis[v]=dis[u]+cost
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,m,c=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
totalcost=0
for i in xrange(m):
    a,b,d=map(int,raw_input().split())
    g[a-1].append([b-1,d])
    g[b-1].append([a-1,d])
    totalcost+=d

pq=[]
dis=dijkstra(0,g)
dis=sorted(dis.items(), key=lambda x:x[1])

ans=float('inf')
visited=[0]*n
for u,x in dis:
    visited[u]=1
    for v,cost in g[u]:
        if visited[v]==1:
            totalcost-=cost
    ans=min(ans,totalcost+c*x)
print ans

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M, C = map(int, input().split())
G = [[] for i in range(N)]
E = []
for i in range(M):
    a, b, d = map(int, input().split()); a -= 1; b -= 1
    G[a].append((b, d))
    G[b].append((a, d))
    E.append((a, b, d))

INF = 10**18
dist = [INF]*N
dist[0] = 0
que = [(0, 0)]
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))

*I, = range(N)
I.sort(key = dist.__getitem__)
K = [0]*N
for i, e in enumerate(I):
    K[e] = i

Q = [0]*N
su = 0
for a, b, d in E:
    if K[a] < K[b]:
        Q[b] += d
    else:
        Q[a] += d
    su += d

ans = 10**18
cu = 0
for v in I:
    x = dist[v]
    cu += Q[v]
    ans = min(ans, C*x + (su - cu))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import heapq

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

n,m,c=map(int,raw_input().split())
g=[[]*n for _ in xrange(n)]
cost=[[10**6]*n for _ in xrange(n)]
totalcost=0
for i in xrange(m):
    a,b,d=map(int,raw_input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    cost[a-1][b-1]=d
    cost[b-1][a-1]=d
    totalcost+=d

pq=[]
dis=dijkstra(0,g,cost)
dis=sorted(dis.items(), key=lambda x:x[1])

ans=float('inf')
visited=[0]*n
for u,x in dis:
    visited[u]=1
    for v in g[u]:
        if visited[v]==1:
            totalcost-=cost[u][v]
    ans=min(ans,totalcost+c*x)
print ans

Submission status: Runtime Error

Solution code:
from collections import deque
import heapq

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

n,m,c=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
totalcost=0
for i in xrange(m):
    a,b,d=map(int,raw_input().split())
    g[a-1].append([b-1,d])
    g[b-1].append([a-1,d])
    totalcost+=d

pq=[]
dis=dijkstra(0,g,cost)
dis=sorted(dis.items(), key=lambda x:x[1])

ans=float('inf')
visited=[0]*n
for u,x in dis:
    visited[u]=1
    for v,c in g[u]:
        if visited[v]==1:
            totalcost-=c
    ans=min(ans,totalcost+c*x)
print ans