Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Minimum Cost Sort

  You are given $n$ integers $w_i (i = 0, 1, ..., n-1)$ to be sorted in ascending order. You can swap two integers $w_i$ and $w_j$. Each swap operation has a cost, which is the sum of the two integers $w_i + w_j$. You can perform the operations any number of times.

  Write a program which reports the minimal total cost to sort the given integers.

Input

  In the first line, an integer $n$ is given. In the second line, $n$ integers $w_i (i = 0, 1, 2, ... n-1)$ separated by space characters are given.

Output

  Print the minimal cost in a line.

Constraints

$1 \leq n \leq 1,000$

$0 \leq w_i\leq 10^4$

$w_i$ are all different

Sample Input 1

5
1 5 3 4 2

Sample Output 1

7

Sample Input 2

4
4 3 2 1

Sample Output 2

10



Sample input:
5
1 5 3 4 2


Sample output:
7

Submission status: Accepted

Solution code:
input()
a=list(map(int,input().split()))
b=sorted(a)
c=0
for i in range(len(a)):
 x=a.index(b[i])
 j=0
 while x>i:
  j+=1
  y=a.index(b[x])
  c+=a[y]
  a[x],a[y]=a[y],a[x]
  x=y
 c+=min(b[i]*j,b[i]*2+b[0]*(j+2))
print(c)

Submission status: Accepted

Solution code:
def solve():
    ans = 0

    B = A[:]
    V = [False] * n

    B.sort()
    for i in range(n):
        T[B[i]] = i
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = 0
        m = 10000  # 10**4
        an = 0
        while True:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
            if V[cur]:
                break
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().split()]
    s = min(A)
    s = min(s, 10000)
    T = [0] * (max(A)+1)
    ans = solve()
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
cost = 0
for i in range(n):
    t = cnt = 0
    x = a.index(b[i])
    while x != i:
        y = a.index(b[x])
        a[x], a[y] = b[x], b[i]
        cnt += 1
        t += b[x] + b[i]
        x = y
    if cnt:
        cost += min(t, (b[i] + b[0]) * 2 + t - (b[i] - b[0]) * cnt)
print(cost)

Submission status: Accepted

Solution code:


SENTINEL = 10**9 + 1


def merge_sort(alist):
    """Sort alist using mergesort.
    Returns a tuple of the number of comparisons and sorted list.

    >>> merge_sort([8, 5, 9, 2, 6, 3, 7, 1, 10, 4])
    (34, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    """
    def _sort(left, right):
        count = 0
        if left + 1 < right:
            mid = (left + right) // 2
            count += _sort(left, mid)
            count += _sort(mid, right)
            count += merge(left, mid, right)

        return count

    def merge(left, mid, right):
        count = 0
        ll = alist[left:mid] + [SENTINEL]
        rl = alist[mid:right] + [SENTINEL]

        i = j = 0
        for k in range(left, right):
            count += 1
            if ll[i] <= rl[j]:
                alist[k] = ll[i]
                i += 1
            else:
                alist[k] = rl[j]
                j += 1

        return count

    comp = _sort(0, len(alist))
    return (comp, alist)


def min_cost(li1, li2):
    """calculate minimum cost to transform li1 into li2.

    >>> min_cost([1, 5, 3, 4, 2], [1, 2, 3, 4, 5])
    7
    >>> min_cost([4, 3, 2, 1], [1, 2, 3, 4])
    10
    """
    def find_moves(i, j):
        start = i
        elems = [i]
        mincost = li1[i]
        minidx = 0

        while j != start:
            if mincost > li1[j]:
                mincost = li1[j]
                minidx = len(elems)
            elems.append(j)
            j = li2.index(li1[j])

        elems = elems[minidx+1:] + elems[:minidx+1]
        if 2 * (mincost + li1[mini]) < (len(elems) - 1) * (mincost - li1[mini]):
            elems.append(mini)
            elems.insert(0, mini)

        q = elems.pop()
        p = elems.pop()
        yield (p, q)
        while len(elems) > 0:
            q = p
            p = elems.pop()
            yield (p, q)


    def move(i, j):
        cost = 0
        for p, q in find_moves(i, j):
            li1[p], li1[q] = li1[q], li1[p]
            cost += li1[p] + li1[q]

        return cost

    assert len(li1) == len(li2)
    size = len(li1)
    totalcost = 0

    for i in reversed(range(size)):
        if li1[i] != li2[i]:
            mini = li1.index(li2[0])
            totalcost += move(li1.index(li2[i]), i)

    return totalcost


def run():
    _ = int(input())  # flake8: noqa
    li = [int(i) for i in input().split()]
    sli = li[:]
    (_, sli) = merge_sort(sli)

    print(min_cost(li, sli))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import copy
n = int(input())
a = list(map(int, input().split()))
b = copy.deepcopy(a)
b.sort()
loop = []
minp = min(a)
t = [0 for i in range(n)]
while True:
    i = t.index(0)
    j = len(loop)
    loop.append([a[i]])
    t[i] = 1
    while True:
        i = b.index(a[i])
        if t[i] == 1:
            break
        t[i] = 1
        loop[j].append(a[i])
    if sum(t) == n:
        break
    j += 1
cost = 0
for i in loop:
    if len(i) == 1:
        continue
    ps = sum(i)
    pl = len(i)
    pm = min(i)
    p1 = ps + (pl - 2) * pm
    p2 = ps + pm + (pl + 1) * minp
    cost += min(p1, p2)
print(cost)

Submission status: Accepted

Solution code:
def solve(A, n, s):
    ans = 0

    V = [False for i in range(n)] # 値が交換済みかどうか
    B = sorted(A)
    T = [None for i in range(10001)]
    for i in range(n):
        T[B[i]] = i
    for i in range(n):
        if V[i]: continue
        cur = i # カーソル(サークル内で動かす)
        S = 0 # サークル内の数字の総和
        m = 10000
        an = 0 # サークルに含まれる数字の数
        while True:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v) # mがサークル内の数字の最小値
            S += v
            cur = T[v]
            if V[cur]: break
        ans += min(S + (an-2)*m, m+S+(an+1)*s)
    return ans

n = int(input())
A = list(map(int, input().split(' ')))
s = min(A)
ans = solve(A, n, s)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))
B = A[:]
B.sort()
C = [True for i in range(n)]
minA = min(A)

j = 0
a = []
total = 0
for i in range(n):
    circle = []
    j = i
    while C[j]:
        C[j] = False
        j = B.index(A[j])
        circle.append(A[j])
    n_c = len(circle)
    if n_c == 2:
        total += (circle[0]+circle[1])
    if n_c > 2:
        minc = min(circle)
        cirSum = sum(circle)
        total += min( cirSum + (n_c-2) * minc , cirSum + minc + (n_c+1)*minA)
    a.append(circle)
    

print(total)

Submission status: Accepted

Solution code:
def make_cyclic(w, v):
    flags = [True] * len(w)

    cyclics = []
    for i in range(len(w)):
        if flags[i]:
            flags[i] = False
            cycle = [w[i]]
            now = w[i]
            while True:
                j = v.index(now)
                if j == i:
                    break
                cycle.append(w[j])
                now = w[j]
                flags[j] = False
            cyclics.append(cycle)

    return cyclics


def min_cost_sort(w):
    v = w.copy()
    v.sort()

    cyclics = make_cyclic(w, v)

    ans = 0
    for cycle in cyclics:
        inner_cycle = min(cycle) * (len(cycle) - 2) + sum(cycle)
        if len(set(w) - set(cycle)) >= 1:
            outer_cycle = min(cycle) + min(set(w) - set(cycle)) * (len(cycle) + 1) + sum(cycle)
        else:
            outer_cycle = inner_cycle + 1
        ans += min(inner_cycle, outer_cycle)

    return ans


n = int(input())
w = [int(x) for x in input().split()]

print(min_cost_sort(w))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def Solve():
    ans = 0
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S, an = 0, 0
        m = VMAX
        while True:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
            if V[cur]:
                break
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans

MAX = 1000
VMAX = 10000

n = int(input())
A = [int(x) for x in input().split()]
s = min(A)
B = sorted(A)
T = [0] * (VMAX + 1)
for i, b in enumerate(B):
    T[b] = i
V =[False] * MAX
ans = Solve()
print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
A = list(map(int,input().split()))

MAX = max(A)
m = min(A)
B = A.copy()
result = 0

def merge(A, left, mid, right):

  global  count

  L = A[left:mid]
  L.append(math.inf)
  R = A[mid:right]
  R.append(math.inf)
  i = 0
  j = 0

  for k in range(left,right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1


def mergeSort(A,left,right):
    if left +1 < right:
        mid = (left+right) // 2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

mergeSort(B,0,n)

T = [None] * (MAX+1)
V = [False] * n
for i in range(n):
    T[B[i]] = i

for i in range(n):
    if V[i]: continue
    cur = i
    ant = 0
    S = 0
    s = MAX
    while(1):
        V[cur] = True
        v = A[cur]
        if v < s:
            s = v
        S += v
        ant += 1

        cur = T[v]
        if V[cur]: break

    result += min(S+(ant-2)*s,S+s+(ant+1)*m)


print(result)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))  # ソート前の並び
B = sorted(A)  # ソート後の並び
c = 0  # 移動コスト

# 1 3 4 ... N 2 -> 1 2 3 4 ... N
# パターンa) 移動すべき要素（グループ）の中での最小(2:B[i]） を使って移動させる
# 1 3 4 2 : スタート
# 1 3 2 4 : <1>
# 1 2 3 4 : <2>
#
# パターンb) 一旦 最小(1:B[0]) と グループ最小(2:B[i]) を交換して始める
# 1 3 4 2 : スタート
# 2 3 4 1 : B[i] + B[0] 追加
# 2 3 1 4 : <1> - (B[i] - B[0])
# 2 1 3 4 : <2> - (B[i] - B[0])
# 1 2 3 4 : B[i] + B[0] 追加

for i in range(N - 1):  # 最後の一つは、手前が揃っていれば揃っている
    t = cnt = 0
    ai = A.index(B[i])  # 並べ替え前の B[i] がいる場所

    while ai != i:  # 並べ替え前と同じでない場合
        y = A.index(B[ai])  # 更に次の
        A[ai], A[y] = B[ai], B[i]  # スワップ
        cnt += 1
        t += B[ai] + B[i]  # このときのコスト
        ai = y
    if cnt:
        # パターンa と パターンb を比較して、コストが小さい方に決める
        c += min(t, (B[i] + B[0]) * 2 + t - (B[i] - B[0]) * cnt)
print(c)

Submission status: Accepted

Solution code:
n = int(input())
w = list(map(int, input().split()))
ws = sorted(w)
d = {v:i for i, v in enumerate(ws)}
checked = [False] * n
cost = 0
wmin = min(w)

for i in range(n):
    if checked[i] or d[w[i]] == i:
        continue
    # 循環群をさがす
    gcnt = 0
    gmin = gtot = w[i]
    nexti = d[w[i]]
    while nexti != i:
        checked[nexti] = True
        gcnt += 1
        gmin = min(gmin, w[nexti])
        gtot += w[nexti]
        nexti = d[w[nexti]]
    cost += gtot + min(gmin * (gcnt - 1), wmin * (gcnt + 2) + gmin)
print(cost)

Submission status: Accepted

Solution code:
def solve(w_list, sort_list):
    ans = 0
    min_num = sort_list[0]
    for i in range(len(w_list)):
        x = sort_list.index(w_list[i])
        if x == i:
            continue
        sum_cost = 0
        min_loop_n = 10**4 + 1
        j = i
        loop_count = 0
        while True:
            loop_count += 1 
            sum_cost += w_list[j]
            min_loop_n = min(min_loop_n, w_list[j])
            if x == i:
                break
            w_list[x], w_list[j] = w_list[j], w_list[x]
            x = sort_list.index(w_list[j])
        ans += min(sum_cost + (loop_count-2)*min_loop_n, sum_cost + min_loop_n + (loop_count+1)*min_num)
    return ans
        
            
            
n = int(input())
w_list = list(map(int, input().split()))
sort_list = sorted(w_list)
print(solve(w_list, sort_list))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)

visited = [0] * n  
idxs = {}  
for i, b in enumerate(B):
    idxs[b] = i

saisyo = min(A)  

ans = 0
for i in range(n):
    if visited[i]:
        continue  
    cur = i  
    S = 0  
    n2 = 0
    m = float("inf")
    while True:
        visited[cur] = True
        S += A[cur]
        m = min(m, A[cur])
        n2 += 1
        cur = idxs[A[cur]]
        if visited[cur]:
            break 
    ans += min(m*(n2-2)+S, m+S+(1+n2)*saisyo)

print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())
a = list(map(int, input().split()))
b= sorted(a)

ans = 0
for i in range(n):
    w = 0
    cnt = 0
    x = a.index(b[i]) # b[i]: sort未済の中で最小値
    while x != i:
        y = a.index(b[x]) #位置xに来るべき数の位置
        a[x], a[y] = b[x], b[i] #b[i] -> 位置yに移動
        cnt += 1
        w += b[x] + b[i]
        x = y
    if cnt > 0: 
        ans += min(w, (b[i] + b[0]) * 2 + w - (b[i] - b[0]) * cnt) #b[0]が全体の最小値

print(ans)

Submission status: Accepted

Solution code:
import copy
INFTY=1000000000
MAX = 1000
VMAX = 100000

def solve(W,N,VMAX):
    T = [-1 for _ in range(VMAX)]
    for i in range(N):
        ans = 0
        V = [False for _ in range(N)]
        WW=copy.deepcopy(W)
        WW.sort()
        for i in range(N):
            T[WW[i]] = i
        for i in range(N):
            if V[i]:
                continue
            cur = i
            S = 0
            m = VMAX
            an = 0
            while True:
                V[cur] = True
                an += 1
                v = W[cur]
                m = min(m,v)
                S += v
                cur = T[v]
                if V[cur]:
                   break
            ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans

N = int(input())
W = list(map(int,input().split()))
s = min(W)
ans = solve(W,N,VMAX)
print(ans)

Submission status: Accepted

Solution code:
mp = {}
MAXN = 1010
mini =  100000
w = [0] * MAXN
done = [False] * MAXN

n = int(input())
w1 = [int(i) for i in input().split()]

for index, value in enumerate(w1):
    w[index] = value

for i in range(n):
    mp[w[i]] = 0
    mini = min(mini, w[i])

k = 0
for i in sorted(w1):
    mp[i] = k
    k += 1

ans = 0
for i in range(n):
    if done[i]: continue
    cnt = 0
    now = i
    mi = 100000
    total = 0
    while (True):
        if done[now]: break
        cnt += 1
        done[now] = True
        mi = min(mi, w[now])
        total += w[now]
        now = mp[w[now]]
    tmp = total + (cnt - 2) * mi
    tmp = min(tmp, total + mi + mini * (cnt + 1))
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_D
# 本の解説がわかりやすい
# ここでは本には書いてないことの補足を意識しながらコメントを付けていく
WMAX = 10**4 + 1
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)
is_visited = [False] * n  # 巡回管理用
next_idxs = {}  # Aの要素について、これのkeyを見れば、その数字がsort後にどの位置にあるのかわかるように対応させる
for i, b in enumerate(B):
    next_idxs[b] = i

m_A = min(A)  # globalで一番小さい要素

# ソート後の並び順から巡回可能なグループから答えを計算する
# グループ内の最小の要素をm, グループの和をS, グループ内の要素数をn2とする。
# 具体的には,m*(n2-2) + S もしくは m + S + (1+n2)*m_Aのうち小さい方
ans = 0
for i in range(n):
    if is_visited[i]:
        continue  # 巡回済みならば次へ
    cur = i  # 巡回制御用のidx #探索済みでないiが入るはず
    S = 0  # 合計管理用
    n2 = 0
    m = WMAX  # グループ内の最小値探索用
    while True:
        # まずはもろもろの値を更新
        is_visited[cur] = True
        S += A[cur]
        m = min(m, A[cur])
        n2 += 1
        # ここで次のidxを取得する
        cur = next_idxs[A[cur]]
        if is_visited[cur]:
            break  # もし一周したらおわり
    # ループ内で完結したほうがいいのか外から要素を変えいてきたほうがいいのか
    # 小さい方を採用して答えに足し込む
    ans += min(m*(n2-2)+S, m+S+(1+n2)*m_A)

print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))
    sorted_elements = sorted(elements)
    total_cost = 0

    for i in range(n - 1):
        cost = 0
        cnt = 0
        x_idx = elements.index(sorted_elements[i])
        while i != x_idx:
            y_idx = elements.index(sorted_elements[x_idx])
            elements[x_idx], elements[y_idx] = (sorted_elements[x_idx],
                                                sorted_elements[i])
            cnt += 1
            cost += sorted_elements[x_idx] + sorted_elements[i]
            x_idx = y_idx
        if cnt:
            total_cost += min(cost,
                              (sorted_elements[i] + sorted_elements[0]) * 2 + cost
                              - (sorted_elements[i] - sorted_elements[0]) * cnt)

    print(total_cost)

Submission status: Accepted

Solution code:
N = int(input())
*W, = map(int, input().split())
C = {w: i for i, w in enumerate(W)}
W.sort()

ans = 0
S = []
used = [0]*N
for i in range(N):
    if used[i]:
        continue
    sq = []
    w = W[i]
    p = i; j = None
    while j != i:
        j = C[w]; w = W[j]
        used[j] = 1
        sq.append(w)
        p = j
    mi = min(sq); ln = len(sq)
    if ln >= 2:
        ans += sum(sq)
    S.append((mi, ln))
S.sort()
m, ln = S[0]
if ln >= 2:
    ans += (ln-2)*m
for mi, ln in S[1:]:
    if ln <= 2:
        continue
    ans += min(m+mi+ln*m, (ln-2)*mi)
print(ans)

Submission status: Accepted

Solution code:

def resolve():
    def solve(n, arr):

        def cycles():
            V = [False]*N
            B = sorted(A)
            T = {B[i]:i for i in range(N)}
            C = []
            for i in range(N):
                if V[i]:
                    continue
                cur = i
                cycle = []
                while not V[cur]:
                    V[cur] = True
                    cycle.append(cur)
                    cur = T[A[cur]]
                C.append(cycle)
            return C

        ans = 0
        minV = min(A)
        for cycle in cycles():
            S = sum([A[i] for i in cycle])
            m = min([A[i] for i in cycle])
            an = len(cycle)
            ans += min(S+(an-2)*m, S+(an+1)*minV+m)
        return ans

    N = int(input())
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def solve(A,n,s):
    ans = 0

    V = [False for i in range(n)] # 値が交換済みかどうか
    B = sorted(A)
    T = [None for i in range(10001)]
    for i in range(n):
        T[B[i]] = i
    for i in range(n):
        if V[i]: continue
        cur = i #カーソル
        S = 0 #サークル内の数字の総和
        m = 10000 # VMAX
        an = 0 # サークルに含まれる数字の個数
        while True: #サークル内の処理
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m,v) #mがサークル内の最小の数字
            S += v
            cur = T[v]
            if V[cur]: break
        ans += min(S+(an-2)*m, m+S+(an+1)*s)
    return ans

n = int(input())
A = [int(x) for x in input().split()]
s = min(A)

ans = solve(A,n,s)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
w = list(map(int,input().split()))
A = dict(zip(sorted(w), w))
min_value = min(A)
A = {k:v for k,v in A.items() if k != v or k == min_value}
totalcost = 0

while len(A) > 1:
    i_move_count = 0
    i = min_value
    if min_value == A[min_value]:
        i = min([v for v in A if v != min_value])

    while A[i] != i:
        j = A[i]
        A[i] = A[j]
        A.pop(j)
        i_move_count += 1
        totalcost += j

    if i != min_value:
        A.pop(i)

    totalcost += min((i * i_move_count), ((min_value * i_move_count) + (min_value + i) * 2))

print(totalcost)

Submission status: Accepted

Solution code:
n = int(input())
w = list(map(int, input().split()))
s = sorted(w)

cost = 0
for i in range(n):
    # 最小の要素と最小の要素の位置に適した要素と交換していく
    now_v = s[i]
    now_idx = w.index(s[i])
    j = 0 # 交換回数
    while now_idx > i:
        j += 1
        target_v = s[now_idx]
        target_idx = w.index(target_v)
        cost += w[target_idx] # ターゲットの方だけ足していく
        w[now_idx], w[target_idx] = w[target_idx], w[now_idx]
        now_idx = target_idx
    # now_v * j: 普通の交換。
    # now_v * 2 + s[0] * (j + 2): 
    #       s[0]は最小値。
    #       最小値と現在値を交換して(コスト: now_v + s[0])、
    #       ソート完了後に(コスト: s[0] * j)
    #       最小値と現在値を元に戻すコスト(コスト: now_v + s[0])。
    #       2回以上ならこっちが少ない。
    cost += min(now_v * j, now_v * 2 + s[0] * (j + 2))
print(cost)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]

done = {}
for i in range(n):
    done[a[i]] = 0
# print(done)

direct = {}
a_sorted = sorted(a)
for i in range(n):
    direct[a_sorted[i]] = i
# print(direct)

group_list = []
for i in range(n):
    if done[a[i]] == 1:
        continue
    else:
        f = a[i]
        done[f] = 1
        group = [f]
        n = f
        while a[direct[n]] != f:
            n = a[direct[n]]
            done[n] = 1
            group.append(n)
        group_list.append(group)
# print(group_list)

m = a_sorted[0]
cost = 0
while len(group_list) > 0:
    group = group_list.pop()
    if len(group) == 1:
        continue
    else:
        cost += min(sum(group) + (len(group) - 2) * min(group), sum(group) + min(group) + (len(group) + 1) * m)
print(cost)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int, input().split()))

def cycle_search(i):
    next_search_ind=i
    ret=[]
    while 1:
        now_ind=next_search_ind
        next_search_ind=sorted_A.index(A[now_ind])
        ret.append(A[now_ind])
        cycle_searched[now_ind]=True
        if cycle_searched[next_search_ind]:
            break
    return ret


sorted_A=sorted(A)

cycles=[]
cycle_searched=[False]*n

for i in range(n):
    if cycle_searched[i] == False:
        cycles.append(cycle_search(i))

ans=0
min_A=sorted_A[0]
for cycle in cycles:
    cycle_len=len(cycle)
    if cycle_len == 1:
        continue
    else:
        ans1 = sum(cycle)+(cycle_len-2)*min(cycle)
        min_cycle=min(cycle)
        ans2 = sum(cycle)-min_cycle+min_A+(cycle_len-2)*min_A+2*(min_A+min_cycle)
        ans += min(ans1,ans2)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
idx = {}
for i, a in enumerate(sorted(arr)):
    idx[a] = i
visit = [False]*n
Min = min(arr)
ans = 0
for i in range(n):
    if visit[i]:
        continue
    visit[i] = True
    now = idx[arr[i]]
    tmp_min = arr[i]
    tot = tmp_min
    cnt = 1
    while now != i:
        visit[now] = True
        tot += arr[now]
        cnt += 1
        if tmp_min > arr[now]:
            tmp_min = arr[now]
        now = idx[arr[now]]
    ans += min(tot + (cnt - 2)*tmp_min, tot + tmp_min + (cnt + 1)*Min)
print(ans)

Submission status: Accepted

Solution code:
WMAX = 10 ** 4 + 1
N = int(input())
W1 = [int(w) for w in input().split()]
W2 = sorted(W1)
W3 = {}
mn1 = min(W1)
V = [False] * N

for i, w in enumerate(W2):  W3[w] = i

cost = 0
for i in range(N):
    if V[i]: continue
    cur = i
    S = 0
    N2 = 0
    mn2 = WMAX
    while True:
        V[cur] = True
        S += W1[cur]
        mn2 = min(mn2, W1[cur])
        N2 += 1
        cur = W3[W1[cur]]
        if V[cur]: break
    cost += min(mn2 * (N2 - 2) + S, mn2 + S + (1 + N2) * mn1)

print(cost)

Submission status: Accepted

Solution code:
n = int(input())
W = list(map(int, input().split()))

_W = W[:]
_W.sort()
m = _W[0]

C = [None for _ in range(_W[n - 1] + 1)]
V = [False for _ in range(_W[n - 1] + 1)]

for i in range(n):
    C[_W[i]] = W[i]

r = 0

for i in _W:
    if V[i]:
        continue
    nxt = C[i]
    V[i] = True
    if nxt == i or V[nxt]:
        continue
    sum_w = i
    min_w = i
    c = 1
    while V[nxt] is False:
        V[nxt] = True
        sum_w += nxt
        nxt = C[nxt]
        c += 1
    r += min(sum_w + (c - 2) * min_w, sum_w + min_w + (c + 1) * m)

print(r)

Submission status: Accepted

Solution code:
WMAX = 10 ** 4 + 1
n = int(input())
A = list(map(int, input().split()))  #1 5 3 4 2
B = sorted(A)  #1 2 3 4 5

is_visited = [False] * n
next_idxs = {}

for i, b in enumerate(B):
  next_idxs[b] = i

m_A = min(A)

ans = 0
for i in range(n):
  if is_visited[i]:
    continue
  cur = i
  S = 0
  n2 = 0
  m = WMAX
  while True:
    is_visited[cur] = True
    S += A[cur]
    m = min(m, A[cur])
    n2 += 1
    cur = next_idxs[A[cur]]
    if is_visited[cur]:
      break
  ans += min(m*(n2-2) + S, m+S+(1+n2)*m_A)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a =list(map(int,input().split()))
b = sorted(a)
c = 0
for i in range(n-1):
    t = cnt = 0
    x = a.index(b[i])
    while x != i:
        y = a.index(b[x])
        a[x],a[y] = b[x],b[i]
        cnt += 1
        t += b[x]+b[i]
        x =y
    if cnt:
        c+= min(t,(b[i]+b[0])*2+t-(b[i]-b[0])*cnt)

print(c)

Submission status: Accepted

Solution code:
# Minimum Cost Sort
# 交換に重みwぶんコストがかかる

# N <= 1000
# a <= 10000

N = int(input())
A = list(map(int, input().split()))
origin = list(range(N))

B = sorted(zip(A, origin), key=lambda x: x[0])


class UnionFind():
    def __init__(self, n):
        self.g = [[i] for i in range(n)]

    def root(self, x):
        if self.is_root(x):
            return x

        self.g[x] = self.root(self.g[x])
        return self.g[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        # yにxをくっつける
        if x < y:
            x, y = y, x
        self.g[y] += self.g[x]
        self.g[x] = y

        return True

    def size(self, x):
        return -self.root(x)

    def is_root(self, x):
        if type(self.g[x]) is list:
            return True
        return False


G = UnionFind(N)
for i, b in enumerate(B):
    G.unite(i, b[1])


min_g = min(A)
cost = 0
for i in range(N):
    if G.is_root(i):
        W = [A[j] for j in G.g[i]]
        n_w = len(W)
        sum_w = sum(W)
        min_w = min(W)

        cost1 = sum_w + min_w*(n_w-2)
        cost2 = cost1 + 2*(min_w + min_g) - (min_w-min_g)*(n_w-1)
        cost += min(cost1, cost2)

print(cost)

Submission status: Accepted

Solution code:

def solve(n,num_list,s):
    ans = 0
    # Vはループを確認する際に回ったかどうかをチェックする
    V = [False for _ in range(n)]
    
    # sorted_num_listでは数列の最終的なゴールを確認する
    sorted_num_list = sorted(num_list)

    # ゴールのインデックスを確認する
    T = [None for _ in range(10000+1)]
    for i in range(n):
        T[sorted_num_list[i]] = i

    # 全ての要素に対して
    for i in range(n):

        # Vが埋まっていれば前ループの要素サイクルで移動済みなので無視
        if V[i]:
            continue

        cur = i
        
        # Sは サイクル内のバリューの合計
        S = 0

        # mはサイクルの最小値
        m = 10000

        # anはサイクルの要素数
        an = 0

        # ここからサイクルごとのループに入る
        while True:
            V[cur] = True
            an += 1
            v = num_list[cur]
            m = min(m,v)
            S += v
            cur = T[v]
            if V[cur]:
                break
        ans += min(S + (an - 2)*m,m+S+(an+1)*s)
    return ans

# 移動先をリストとしてバリューをインデックスにして保管するやり方をマスターすべし，


if __name__ == "__main__":
    n = int(input())
    num_list = list(map(int,input().split()))
    s = min(num_list)
    ans = solve(n,num_list,s)
    print(ans)

Submission status: Accepted

Solution code:
import bisect


def sorted_index(A):
    # Aをソートした後のindexのリスト
    A_ = sorted(A)
    B = []
    for a in A:
        idx = bisect.bisect_left(A_, a)
        B.append(idx)
    return B


def cyclic_factorize(A):
    # Aを巡回置換分解する
    B = sorted_index(A)
    checked = [False] * len(A)
    cycle_lst = []
    for i, a in enumerate(A):
        if checked[i]:
            continue
        now = i
        checked[now] = True
        cycle = [a]
        next = B[now]
        while not checked[next]:
            now = next
            next = B[now]
            cycle.append(A[now])
            checked[now] = True
        cycle_lst.append(cycle)
    return cycle_lst


N = int(input())
*W, = map(int, input().split())
cycle_lst = cyclic_factorize(W)
ans = 0
global_min = min(W)
for cycle in cycle_lst:
    l = len(cycle)
    s = sum(cycle)
    local_min = min(cycle)
    ans += s + min((l - 2) * local_min, local_min + (l + 1) * global_min)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
*W, = map(int, input().split())
C = {w: i for i, w in enumerate(W)}
W.sort()

ans = 0
S = []
used = [0]*N
for i in range(N):
    if used[i]:
        continue
    sq = []
    w = W[i]
    p = i; j = None
    while j != i:
        j = C[w]; w = W[j]
        used[j] = 1
        sq.append(w)
        p = j
    mi = min(sq); ln = len(sq)
    if ln >= 2:
        ans += sum(sq)
    S.append((mi, ln))
S.sort()
m, ln = S[0]
if ln >= 2:
    ans += (ln-2)*m
for mi, ln in S[1:]:
    if ln <= 2:
        continue
    ans += min(m+mi+ln*m, (ln-2)*mi)
print(ans)

Submission status: Accepted

Solution code:
WMAX = 10**4 + 1
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)
is_visited = [False] * n  # 巡回管理用
next_idxs = {}  # Aの要素について、これのkeyを見れば、その数字がsort後にどの位置にあるのかわかるように対応させる
for i, b in enumerate(B):
    next_idxs[b] = i

m_A = min(A)  # globalで一番小さい要素

# ソート後の並び順から巡回可能なグループから答えを計算する
# グループ内の最小の要素をm, グループの和をS, グループ内の要素数をn2とする。
# 具体的には,m*(n2-2) + S もしくは m + S + (1+n2)*m_Aのうち小さい方
ans = 0
for i in range(n):
    if is_visited[i]:
        continue  # 巡回済みならば次へ
    cur = i  # 巡回制御用のidx #探索済みでないiが入るはず
    S = 0  # 合計管理用
    n2 = 0
    m = WMAX  # グループ内の最小値探索用
    while True:
        # まずはもろもろの値を更新
        is_visited[cur] = True
        S += A[cur]
        m = min(m, A[cur])
        n2 += 1
        # ここで次のidxを取得する
        cur = next_idxs[A[cur]]
        if is_visited[cur]:
            break  # もし一周したらおわり
    # ループ内で完結したほうがいいのか外から要素を変えいてきたほうがいいのか
    # 小さい方を採用して答えに足し込む
    ans += min(m*(n2-2)+S, m+S+(1+n2)*m_A)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
c = 0
for i in range(n):
    x = a.index(b[i])
    j = 0
    while x > i:
        j += 1
        y = a.index(b[x])
        c += a[y]
        a[x],a[y] = a[y],a[x]
        #print(" ".join(map(str,a)))
        #print(f"x:{x} y:{y}")
        x = y
    c += min(b[i]*j,b[i]*2+b[0]*(j+2))
print(c)

Submission status: Accepted

Solution code:
def minimum_cost_sort():
    sorted_positions = {str(val):i for i, val in enumerate(sorted(W))}
    is_passed = [False]*n
    minimum_weight = min(W)
    ans = 0
    for i in range(n):
        if is_passed[i]:
            continue
        pointer = i
        total_weight = 0
        local_minimum_weight = 10000
        counter = 0
        while not is_passed[pointer]:
            is_passed[pointer] = True
            total_weight += W[pointer]
            local_minimum_weight = min(local_minimum_weight, W[pointer])
            pointer = sorted_positions[str(W[pointer])]
            counter += 1
        ans += min(total_weight+local_minimum_weight*(counter-2), total_weight+minimum_weight*(counter+1)+local_minimum_weight)
    print(ans)

if __name__ == "__main__":
    n = int(input())
    W = list(map(int, input().split()))
    minimum_cost_sort()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)
m_A = B[0]

next_idxs = {}
for i in range(n):
    next_idxs[B[i]] = i

ans = 0
is_visited = [False] * n

for i in range(n):
    if is_visited[i]:
        continue
    cur = i
    S = 0
    n2 = 0
    m = A[i]
    while True:
        is_visited[cur] = True
        S = S + A[cur]
        m = min(m, A[cur])
        n2 = n2 + 1
        cur = next_idxs[A[cur]]
        if is_visited[cur]:
            break
    ans = ans + min(m*(n2-2)+S, m + S + (n2+1)*m_A)

print(ans)