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:
# -*- coding: utf-8 -*-
import copy

class BagsWithWeight(list):
    def __init__(self, l):
        super(BagsWithWeight, self).__init__(l)
        self.sorted_weights = list(sorted(self))

    def get_lists_of_loop(self):
        """???????????????????????????????????????????±??????????
        ????????\??????????????????????????????????????¬??\???????????? index ???????????????????????????
        ??????????????????????????¬??\???????????? index ????????£???????????¨?????????????????????????????????
        ?????????????????§?????????????????????????????¨ 1 ????????????????????????
        ????????????????????????????????? 1 ????????\???????????§??????????????????????????????????????????
        out: ListOfLoops     ??¨?????? loop ????????????
        """
        c_weights = copy.copy(self)
        loops = Loops()
        for i in range(len(self)):
            loop = []
            index = i
            while c_weights[index] != -1:
                loop.append(c_weights[index])
                c_weights[index] = -1
                index = self.get_index_of_sorted_bag(index)
            if loop:
                loops.append(loop)
        return loops

    def get_index_of_sorted_bag(self, index):
        """???????????????????????????????????????????????? index ????????????
        in:  index    int    ??????????????? index ????±?????????????????????? index
        out: int    ?????????????????????????????? index
        """
        return self.sorted_weights.index(self[index])


class Loops(list):
    def append(self, elm):
        elm.sort()
        elm = Loop(elm, self)
        super(Loops, self).append(elm)

    def get_minimum_element(self):
        return min(min(self))

    def get_cost(self):
        return sum(map((lambda loop: loop.get_cost_of_sorting()), self))


class Loop(list):
    def __init__(self, loop, loops):
        super(Loop, self).__init__(loop)
        self.loops = loops
    
    def get_minimum_weight_of_outer(self):
        return self.loops.get_minimum_element()

    def get_cost_of_sorting(self):
        """Loop ?????¨???????°??????????????±??????????
        """
        cost = sum(self) + min(self) * (len(self) - 2)
        cost_reduced = self.get_how_much_outer_minimum_weight_bag_reduces_cost()
        if cost_reduced > 0:
            return cost - cost_reduced
        else:
            return cost


    def get_how_much_outer_minimum_weight_bag_reduces_cost(self):
        """Loops ???????°????????????????????????£???????????§???????????????????±??????????
        List of Loops ??????????°?????????????????´????
        Loop ??????????°?????????????????´???¨??\????????????
        ?????????????????£?????????????????§???????????????????????????
        ??????????????? len(loop) - 1 ??????????????????????????????????°???????????????????????????????
        out: int    ????????§???????????????
        """
        return ((min(self) - self.get_minimum_weight_of_outer()) *
                    (len(self) - 1) -
                    (min(self) + self.get_minimum_weight_of_outer()) * 2)


def get_weights():
    raw_input()
    return map(int, raw_input().split())

bww = BagsWithWeight(get_weights())
loops = bww.get_lists_of_loop()
print loops.get_cost()

Submission status: Accepted

Solution code:
"""Minimum cost Sort."""

def make_cycle(A):
    """Return a list which has the minimum element of A and
    switch elements cycles as list.

    A is a list whose elements' type is 'int'.

    Each cycle list has its minimum elements in the first index.
    """
    B = list(A)
    B.sort()
    cycle_list = [B[0]]
    for i, b in enumerate(B):
        if b != None:
            new_cycle = []
            new_cycle.append(b)
            B[i] = None
            si = A.index(b)
            while si != i:
                st = B[si]
                new_cycle.append(st)
                B[si] = None
                si = A.index(st)
            cycle_list.append(new_cycle)
    return cycle_list

def min_sorting_cost(A):
    """Return the minimum cost of sorting A.

    A is a list whose elements' type is 'int'.
    """
    cycles = make_cycle(A)
    min_w = cycles[0]
    cost = 0
    for c in cycles[1:]:
        n = len(c)
        min_cw = c[0]
        dec = (n - 1) * (min_cw - min_w)
        inc = 2 * (min_w + min_cw)
        if dec < inc:
            cost += sum(c) + min_cw * (n - 2)
        else:
            cost += sum(c) + min_cw * (n - 2) - dec + inc
    return cost


n = int(input())

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

ans = min_sorting_cost(A)

print(ans)

Submission status: Accepted

Solution code:
"""Minimum cost Sort."""

def min_cost_sort(A):
    """Sort list A in ascending order.
 
    And return the switching cost in sorting.
    """
    B = list(A)
    B.sort()
    cost = 0
    min_w = B[0]
    for i, b in enumerate(B):
        tmp_cost = 0
        bi = A.index(b)
        n = 1
        while bi != i:
            n += 1
            st = B[bi]
            si = A.index(st)
            tmp_cost += b + st
            A[bi], A[si] = st, b
            bi = si
        dec = (n - 1) * (b - min_w)
        inc = 2 * (min_w + b)
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost


n = input()

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

ans = min_cost_sort(A)

print(ans)

Submission status: Accepted

Solution code:
"""Minimum cost Sort."""

def min_cost_sort(A):
    """Sort list A in ascending order.
 
    And return the switching cost in sorting.
    """
    B = list(A)
    B.sort()
    cost = 0
    min_w = B[0]
    for i, b in enumerate(B):
        tmp_cost = 0
        bi = A.index(b)
        cnt = 0
        while bi != i:
            cnt += 1
            st = B[bi]
            si = A.index(st)
            tmp_cost += b + st
            A[bi], A[si] = st, b
            bi = si
        if cnt:
            dec = cnt * (b - min_w)
            inc = 2 * (min_w + b)
            if dec < inc:
                cost += tmp_cost
            else:
                cost += tmp_cost - dec + inc
    return cost


n = input()

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

ans = min_cost_sort(A)

print(ans)

Submission status: Accepted

Solution code:
"""Minimum cost Sort."""

def min_cost_sort(A):
    """Sort list A in ascending order.
 
    And return the switching cost in sorting.
    """
    B = list(A)
    B.sort()
    cost = 0
    min_w = B[0]
    for i, b in enumerate(B):
        tmp_cost = 0
        bi = A.index(b)
        cnt = 0
        while bi != i:
            cnt += 1
            st = B[bi]
            si = A.index(st)
            tmp_cost += b + st
            A[bi], A[si] = st, b
            bi = si
        dec = cnt * (b - min_w)
        inc = 2 * (min_w + b)
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost


n = input()

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

ans = min_cost_sort(A)

print(ans)

Submission status: Accepted

Solution code:
n = int(raw_input())
W = map(int, raw_input().split())
s = min(W)
T = [0] * (max(W)+1)

def solve():
    ans = 0
    B = W[:]
    V = [False] * n

    B.sort()
    for i in xrange(n):
        T[B[i]] = i
    for i in xrange(n):
        if V[i]:
            continue
        cur = i
        S = 0
        m = max(W)+1
        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

def main():
    ans = solve()
    print ans
    return 0

main()

Submission status: Accepted

Solution code:
n = int(raw_input())
W = map(int, raw_input().split())
s = min(W)
T = [0] * (max(W)+1)

def solve():
    ans = 0
    B = W[:]
    V = [False] * n

    B = sorted(B)
    for i in xrange(n):
        T[B[i]] = i
    for i in xrange(n):
        if V[i]:
            continue
        cur = i
        S = 0
        m = max(W)+1
        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

def main():
    ans = solve()
    print ans
    return 0

main()

Submission status: Accepted

Solution code:
n, cost = int(input()), 0
num = list(map(int, input().split()))
num_s = sorted(num)
n0 = num_s[0]

for i in range(n - 1):
    ni, tmp, cnt = num_s[i], 0, 0
    si = num.index(ni)
    while si != i:
        nsi = num_s[si]
        sj = num.index(nsi)
        num[si], num[sj] = nsi, ni
        tmp += ni + nsi
        cnt += 1
        si = sj
    if cnt:
        cost += min(tmp, (ni + n0) * 2 + tmp - (ni - n0) * cnt)
print(cost)

Submission status: Accepted

Solution code:
import sys

def minimumCostSort(A):
    B = sorted(A)
    V = [False] * len(A)
    T = [0] * 10001
    ans = 0
    s = min(A)

    for i in range(len(A)):
        T[B[i]] = i

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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    print minimumCostSort(A)

Submission status: Accepted

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

    B = A[:]
    V = [False for i in A]
    B = sorted(B)
    T = [0 for i in range(VMAX+1)]
    for i in range(n):
        T[B[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 = 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 = list(map(int, input().split()))

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

Submission status: Accepted

Solution code:
#coding:UTF-8
def MCS(A,n):
    B=sorted(A)
    B0=B[0]
    cost=0
    for i in range(n-1):
        Bi,t_cost,count=B[i],0,0
        si=A.index(Bi)
        while si!=i:
            bsi=B[si]
            sj=A.index(bsi)
            A[si],A[sj]=bsi,Bi
            t_cost+=Bi+bsi
            count+=1
            si=sj
        if count:
            cost+=min(t_cost,(Bi + B0) * 2 + t_cost - (Bi - B0) * count) 
    print(cost)
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    MCS(A,n)

Submission status: Accepted

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

def processA(target_list, correct_list, i):

    cost = 0
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
        #print("A", target_list)
    return cost
    
def processB(target_list, correct_list, i):
    minv = correct_list[0]
    target = correct_list[i]

    if minv == target:
        return 10 ** 9
    cost = (minv + target)
    #print(minv, target)
    mmi = target_list.index(minv)
    smi = target_list.index(target)
    target_list[mmi], target_list[smi] = target_list[smi], target_list[mmi]
    
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(minv)
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
        #print("B",target_list)
    return cost
    
def minimum_cost_sort(target_list):
    correct_list = sorted([a for a in target_list])
    cost = 0
    i = 0
    while not correct_list == target_list:
        cost_b = processB([a for a in target_list], correct_list, i)
        cost_a = processA(target_list, correct_list, i)
        cost += min(cost_a, cost_b)
        #print(cost_a, cost_b)
        #print(target_list)
        i += 1
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import functools

def find_all_rings(items):
    "items: (??°???, ?????????????????????????????????)"
    l = len(items)
    check_list = [False] * l
    rings = []
    i = 0
    while i < l:
        if check_list[i] == False:
            ring = []
            first = items[i]
            ring.append(first)
            check_list[i] = True
            item_index = first[1]
            item = items[item_index]
            while item[0] != first[0]:
                ring.append(item)
                check_list[item_index] = True
                item_index = item[1]
                item = items[item_index]
            rings.append(ring)
        i += 1
    return rings

def compute_ring_cost(min_all, ring):
    l = len(ring)
    if l <= 1:
        return 0
    w = [item[0] for item in ring]
    min_ring = min(w)
    sum_ring = sum(w)
    if (l + 1) * min_all < (l - 3) * min_ring:
        return sum_ring + min_ring + (l + 1) * min_all
    else:
        return sum_ring + (l - 2) * min_ring

n = int(input())
ns = list(map(int, input().split()))
items = []
sorted_items = []
for i in range(n):
    item = (ns[i], i)
    items.append(item)
    sorted_items.append(item)

sorted_items.sort(key = lambda x : x[0])

for i in range(n):
    item = sorted_items[i]
    items_index = item[1]
    items[items_index] = (item[0], i)

rings = find_all_rings(items)
compute_ring_cost1 = functools.partial(compute_ring_cost, min(ns))
print(sum(map(compute_ring_cost1, rings)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

MAX_VALUE = int(1e4 + 1)


def min_cost_sort():
    ans = 0
    for i in range(array_length):
        if check_order[i]:
            continue
        current_index = i
        circle_sum, circle_min, circle_size = 0, MAX_VALUE, 0
        while True:
            check_order[current_index] = True
            circle_size += 1
            current_value = array[current_index]
            circle_min = min(circle_min, current_value)
            circle_sum += current_value
            current_index = kv_reverse[current_value]
            if check_order[current_index]:
                break
        ans += min(circle_sum + (circle_size - 2) * circle_min,
                   circle_sum + circle_min + (circle_size + 1) * min_value)
    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length

    check_order = [False] * array_length
    kv_reverse = [-1] * MAX_VALUE
    compare_ans = sorted(array)
    min_value = compare_ans[0]
    for j in range(array_length):
        kv_reverse[compare_ans[j]] = j
    print(min_cost_sort())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

MAX_VALUE = int(1e4 + 1)


def min_cost_sort():
    ans = 0
    for i in range(array_length):
        if check_order[i]:
            continue
        current_index = i
        circle_sum, circle_min, circle_size = 0, MAX_VALUE, 0
        while True:
            check_order[current_index] = True
            circle_size += 1
            current_value = array[current_index]
            circle_min = min(circle_min, current_value)
            circle_sum += current_value
            current_index = value_to_index[current_value]
            if check_order[current_index]:
                break
        ans += min(circle_sum + (circle_size - 2) * circle_min,
                   circle_sum + circle_min + (circle_size + 1) * min_value)
    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length

    check_order = [False] * array_length
    value_to_index = dict()
    compare_ans = sorted(array)
    min_value = compare_ans[0]
    for j in range(array_length):
        value_to_index[compare_ans[j]] = j
    print(min_cost_sort())

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:
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
    c+=min(t,(b[i]+b[0])*2+t-(b[i]-b[0])*cnt)
print(c)

Submission status: Accepted

Solution code:


MAX_NUM = int(1E4 + 1)

if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().strip().split()]
    sorted_A = sorted(A)
    smallest = sorted_A[0]
    correct_pos = [0] * MAX_NUM
    flag_A = [False] * MAX_NUM
    for i, val in enumerate(sorted_A):
        correct_pos[val] = i

    ans = 0
    for i in range(len(A)):
        if flag_A[A[i]]:
            continue
        next_pos = i
        sum = 0
        m = 1E4
        an = 0
        while True:
            an += 1
            val = A[next_pos]
            sum += val
            m = min([m, val])
            flag_A[A[next_pos]] = True
            next_pos = correct_pos[val]
            if flag_A[A[next_pos]]:
                break
        ans += min([sum + (an - 2) * m, m + sum + (an + 1) * smallest])

    print(ans)

Submission status: Accepted

Solution code:
def minimum_cost_sort(A):
  cost = 0
  B = sorted(A)
  for i in range(len(B)):
    x = A.index(B[i])
    cnt = 0
    tmp = 0
    while x != i:
      y = A.index(B[x])
      A[x], A[y] = A[y], A[x]
      tmp += A[x] + A[y]
      cnt += 1
      x = y
    if cnt > 0:
      # compare with procedure as follows:
      #   convert B[i] and B[0] (minimum item) : cost = B[i] + B[0]
      #   sort with B[0] in the same way       : cost diff = (B[i] - B[0]) * cnt
      #   reconvert B[0] and B[i]              : cost = B[i] + B[0]
      cost += min(tmp, (B[i] + B[0]) * 2 + tmp - (B[i] - B[0]) * cnt)
  return cost

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

Submission status: Accepted

Solution code:
MAX = 1000
VMAX = 10000
n = int(input())
A = [int(i) for i in input().split()]
V = [False] * MAX
def solve():
    B = A[:]
    T = [0] * (VMAX + 1)
    B.sort()
    ans = 0
    s = min(VMAX, min(A))
    for i in range(n):
        T[B[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 = 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)
    print(ans)
solve()

Submission status: Accepted

Solution code:
def mklist(B,D,V):
    min = 10000
    for key,val in enumerate(B):
        D[val] = key
        V[val] = 0
        if min > val:
            min = val
    return min

def solve(A,V,D,min):
    cost = 0
    for key, val in enumerate(A):
        if V[val] != 0:
            continue
        W = []
        wmin = 10000
        tw = 0
        k1 = key
        v = val
        while(1):
            k2 = D[v]
            if V[v] == 1:
                break
            W.append(v)
            V[v] = 1
            if wmin > v:
                wmin = v
            tw += v
            #print("key={} k1={} k2={} v={} Vv={}".format(key,k1,k2,v,V[v]))
            k1 = k2
            v = A[k1]
        n = len(W)
        t1 = tw + ((n - 2) * wmin)
        t2 = tw + wmin + ((n + 1) * min)
        if t1 < t2:
            cost += t1
        else:
            cost += t2
    return cost

def main():
    num = int(input())
    A = list(map(int,input().split()))
    B = sorted(A)
    D = {}
    V = {}
    min = mklist(B,D,V)
    cost = solve(A,V,D,min)
    print(cost)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def mincost(A):
    B = sorted(A)
    cost = 0
    
    for i, bi in enumerate(B):
        t = 0
        j = A.index(bi)
        tmp_cost = 0
        
        # swap in a cyclic group
        while j != i:
            t += 1
            bj = B[j]
            k = A.index(bj)
            tmp_cost += bi + bj
            swap(A,j,k)
            j = k
        
        # diff. to swap with min(B)
        dec = t * (bi - B[0])
        inc = 2 * (bi + B[0])
        
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    cost = mincost(A)
    print(cost)

Submission status: Accepted

Solution code:
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def mincost(A):
    B = sorted(A)
    cost = 0
    b0 = B[0]
    
    for i, bi in enumerate(B):
        t = 0
        j = A.index(bi)
        tmp_cost = 0
        
        # swap in a cyclic group
        while j != i:
            t += 1
            bj = B[j]
            k = A.index(bj)
            tmp_cost += bi + bj
            swap(A,j,k)
            j = k
        
        # diff. to swap with min(B)
        dec = t * (bi - b0)
        inc = 2 * (bi + b0)
        
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    cost = mincost(A)
    print(cost)

Submission status: Accepted

Solution code:
n = int(input())
line = input()
L = [int(x) for x in line.split()]

flags = [False] * n
loops = []

S = sorted(L)
I = [S.index(x) for x in L]
for idx, x in enumerate(I):
    if flags[x]:
        continue
    if x == idx:
        flags[idx] = True
        continue

    ws = []
    while S[x] not in ws:
        flags[x] = True
        ws.append(S[x])
        x = I[x]
    loops.append(ws)

cost = 0
for loop in loops:
    a = sum(loop) + (len(loop) - 2) * min(loop)
    b = sum(loop) + min(loop) + (len(loop) + 1) * min(L)
    cost += min(a, b)

print(cost)

Submission status: Accepted

Solution code:
n = int(input())
line = input()
L = [int(x) for x in line.split()]

flags = [False] * n
loops = []

S = sorted(L)
for idx, x in enumerate(L):
    k = S.index(x)
    if flags[k]:
        continue
    if k == idx:
        flags[k] = True
        continue

    ws = []
    while x not in ws:
        flags[k] = True
        ws.append(x)
        x = L[k]
        k = S.index(x)
    loops.append(ws)

cost = 0
for ws in loops:
    n = len(ws)
    a = sum(ws) + (n - 2) * min(ws)
    b = sum(ws) + min(ws) + (n + 1) * min(L)
    cost += min(a, b)

print(cost)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


if __name__ == '__main__':

    n = int(input())
    A = [int(a) for a in input().split(" ")]
    B = A.copy()
    B.sort()
    V = [False]*n
    T = {B[i]:i for i in range(n)}

    ans = 0
    s = min(A)

    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = 0 # sum of weight
        m = 10000 # min of cycle(init max weight)
        an = 0 # length of cycle
        while not V[cur]:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
        ans += min(S + (an - 2)*m, m + S + (an + 1)*s)

    print(ans)

Submission status: Accepted

Solution code:
VMAX = 10000
n = int(input())
A = list(map(int, input().split()))
s = min(A)
def solve():
    ans = 0
    V = [False] * n
    B = sorted(A)
    T = [0] * (VMAX + 1)
    for i in range(n):
        T[B[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 = 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
print(solve())

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
s = min(A)
def solve():
    ans = 0
    V = [False] * n
    B = sorted(A)
    T = {B[i]: i for i in range(n)}
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = an = 0
        m = 10000
        while not V[cur]:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans
print(solve())

Submission status: Accepted

Solution code:
def decode():
    n = int(input())
    w = [int(x) for x in input().split()]

    return n, w


def search(w, sw, swi):
    wi = w.index(sw[swi])
    cost = 0
    count = 0
    while wi != swi:
        tw = sw[wi]
        ti = w.index(tw)
        w[ti], w[wi] = w[wi], w[ti]
        cost += w[ti] + w[wi]
        count += 1
        wi = ti
    return cost, count


def search_min_cost(w):
    sorted_w = list(w)
    sorted_w.sort()

    min_w = sorted_w[0]
    cost = 0

    for i, sww in enumerate(sorted_w):
        tmp_cost, count = search(w, sorted_w, i)
        cost += min(tmp_cost, tmp_cost + (min_w + sww) * 2 - (sww - min_w) * count)

    return cost


if __name__ == '__main__':

    n, w = decode()
    print(search_min_cost(w))

Submission status: Accepted

Solution code:
def calc_cost(hoge):
    cost = 0
    hoge_refer = sorted(hoge[:])
    #checker true means that this index have already looked.
    checker = [False] * len(hoge)
    #abs_min is minimum num in input array.
    abs_min = hoge_refer[0]
    #indexer -> key: sorted val, val: zero 2 n-1
    indexer = {hoge_refer[i]:i for i in range(len(hoge_refer))}
    
    for now_index in range(len(hoge)):
        if checker[now_index]:
            continue
        current = now_index
        size = 0
        sum_num = 0
        circle_min = 10 ** 4
        while True:
            checker[current] = True
            size += 1
            val = hoge[current]
            circle_min = min(circle_min, val)
            sum_num += val
            current = indexer[val]
            if checker[current]:
                break
        cost += min(sum_num+(size-2)*circle_min, circle_min+sum_num+(size+1)*abs_min)
    return cost
        
    
if __name__ == '__main__':
    _ = int(input())
    hoge = [int(x) for x in input().split()]
    print(calc_cost(hoge))

Submission status: Accepted

Solution code:
input()
w=list(map(int,input().split()))
x=min(w)
m={k:v for k,v in zip(sorted(w),w)if k!=v}
l=list(m.keys())
p=[]
while l:
 a=l.pop();b=m[a];l.remove(b)
 if a==m[b]:p+=[[a,b]]
 else:
  t=[b]
  while 1:
   c=m[b];t+=[c]
   if c==a:p+=[t];break
   else:b=c;l.remove(c)
n=0
for s in p:
 n+=sum(s);t=len(s);y=min(s)
 if t>2:n+=min((t-2)*y,y+(t+1)*x)
print(n)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
 
 
WAIT, PRESORT, SORTED = 0, 1, 2
cost = 0
 
def swap(w1, w2):
    global cost
    cost += w1[WAIT] + w2[WAIT]
    w1[PRESORT], w2[PRESORT] = w2[PRESORT], w1[PRESORT]
     
 
n = input()
w = [[wi, i, None] for i, wi in enumerate(map(int, input().split()))]
s = sorted(w)
minw = s[0]
for i, wi in enumerate (s):
    wi[SORTED] = i
     
for si in s:
    tmp = si
    t = []
    while tmp[SORTED] != si[PRESORT]:
        tmp = w[tmp[SORTED]]
        t += [tmp]
 
    if len(t ) and minw != si and si[WAIT] * (len(t) - 2) > minw[WAIT] * (len(t) + 2):
        swap(minw, si)
        for ti in t[::-1]:
            swap(minw, ti)
        swap(minw, si)
    else:
        for ti in t[::-1]:
            swap(si, ti)
     
print(cost)

Submission status: Accepted

Solution code:
input()
w=list(map(int,input().split()))
x=min(w)
m={k:v for k,v in zip(sorted(w),w)if k!=v}
l=list(m.keys())
n=0
while l:
 a=l.pop();b=m[a];l.remove(b)
 if a==m[b]:n+=a+b
 else:
  t=[b]
  while 1:
   c=m[b];t+=[c]
   if c==a:p,q=len(t),min(t);n+=sum(t)+min((p-2)*q,q+(p+1)*x);break
   else:b=c;l.remove(c)
print(n)

Submission status: Accepted

Solution code:
input()
w=list(map(int,input().split()))
s=sorted(w)
x=s[0]
m={k:v for k,v in zip(s,w)if k!=v}
l=list(m.keys())
n=0
while l:
 a=l.pop();b=m[a];l.remove(b)
 if a==m[b]:n+=a+b
 else:
  t=[b]
  while 1:
   c=m[b];t+=[c]
   if c==a:p,q=len(t),min(t);n+=sum(t)+min((p-2)*q,q+(p+1)*x);break
   else:b=c;l.remove(c)
print(n)

Submission status: Accepted

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

Submission status: Accepted

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

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]
  x=y
 c+=min(b[i]*j,b[i]*2+b[0]*(j+2))
print(c)

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]
  x=y
 c+=min(b[i]*j,b[i]*2+b[0]*(j+2))
print(c)