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: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????
def partition(target_list, l, r):
    x = target_list[r]
    i = l - 1

    for j in range(l, r):
        if target_list[j] <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)

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)
    
    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(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("B",target_list)
    return cost
    
def minimum_cost_sort(target_list):
    correct_list = [a for a in target_list]
    quick_sort(correct_list, 0, len(correct_list) - 1)
    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: Wrong Answer

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
        _sum, min_value, circle_size = 0, MAX_VALUE, 0
        while True:
            check_order[current_index] = True
            circle_size += 1
            current_value = array[current_index]
            min_value = min(min_value, current_value)
            _sum += current_value
            current_index = kv_reverse[current_value]
            if check_order[current_index]:
                break
        ans += min(_sum + (circle_size - 2) * min_value, _sum + min_value + (circle_size + 1) * _sum)
    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)
    for j in range(array_length):
        kv_reverse[compare_ans[j]] = j
    print(min_cost_sort())

Submission status: Wrong Answer

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[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: Wrong Answer

Solution code:
def partition(A, l, r):
  p = A[r]
  j = l - 1
  for i in range(l, r):
    if A[i] <= p:
      j += 1
      A[j], A[i] = A[i], A[j]
  j += 1
  A[j], A[r] = A[r], A[j]
  return j

def quick_sort(A, l, r):
  if l < r:
    p = partition(A, l, r)
    quick_sort(A, l, p - 1)
    quick_sort(A, p + 1, r)

def minimum_cost_sort(A):
  cost = 0
  B = A[:]
  quick_sort(A, 0, len(A) - 1)
  for i in range(len(A) // 2):
    if A[i] != B[i]:
      cost += A[i] + B[i]
  return cost

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

Submission status: Wrong Answer

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:
      cost += tmp
      #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: Wrong Answer

Solution code:
# L = [int(x) for x in "1 5 3 4 2".split()]
# n = len(L)

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

flags = [False] * n
loops = []

for i, x in enumerate(L):
    k = x-1
    if flags[k]:
        continue
    if i == k:
        flags[i] = True
        continue

    loop = []
    while k not in loop:
        flags[k] = True
        loop.append(k)
        k = L[k]-1
    loops.append(loop)


cost = 0
for loop in loops:
    cost += min(loop) * len(loop) + sum(loop)

print(cost)

Submission status: Wrong Answer

Solution code:
# line = "10 7 8 9"
# L = [int(x) for x in line.split()]
# n = len(L)

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

flags = [False] * n
loops = []

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

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

cost = 0
for loop in loops:
    m = min(loop)
    cost += m * (len(loop)-1) + sum(loop) - m

print(cost)

Submission status: Wrong Answer

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=[a,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: Wrong Answer

Solution code:
def partition(li, p, r):
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1
    for j in range(p, r):
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

    i += 1
    li[i], li[r] = li[r], li[i]

    return i


def quicksort(li, p, r):
    """sort li by quick sort algorithm.

    >>> li = [3, 2, 1, 3, 2, 1]
    >>> quicksort(li, 0, 5)
    >>> li
    [1, 1, 2, 2, 3, 3]
    """
    if p < r:
        q = partition(li, p, r)
        quicksort(li, p, q-1)
        quicksort(li, q+1, r)


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
    """
    assert len(li1) == len(li2)
    size = len(li1)
    cost = 0
    for i in reversed(range(size)):
        e1 = li1[i]
        e2 = li2[i]
        if e1 == e2:
            continue

        j = li1.index(e2)
        li1[i], li1[j] = li1[j], li1[i]
        cost += e1 + e2

    return cost


def run():
    _ = int(input())  # flake8: noqa
    li = [int(i) for i in input().split()]
    sli = li[:]
    quicksort(sli, 0, len(li)-1)

    print(min_cost(li, sli))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:

def partition(li, p, r):
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1
    for j in range(p, r):
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

    i += 1
    li[i], li[r] = li[r], li[i]

    return i


def quicksort(li, p, r):
    """sort li by quick sort algorithm.

    >>> li = [3, 2, 1, 3, 2, 1]
    >>> quicksort(li, 0, 5)
    >>> li
    [1, 1, 2, 2, 3, 3]
    """
    if p < r:
        q = partition(li, p, r)
        quicksort(li, p, q-1)
        quicksort(li, q+1, r)



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 move(i, j):
        cost = 0
        k = li2.index(li1[j])
        if li1[j] > li1[k]:
            cost += move(j, k)

        li1[i], li1[j] = li1[j], li1[i]
        return cost + li1[i] + li1[j]

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

    for i in reversed(range(size)):
        if li1[i] != li2[i]:
            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[:]
    quicksort(sli, 0, len(li)-1)

    print(min_cost(li, sli))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:

def partition(li, p, r):
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1
    for j in range(p, r):
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

    i += 1
    li[i], li[r] = li[r], li[i]

    return i


def quicksort(li, p, r):
    """sort li by quick sort algorithm.

    >>> li = [3, 2, 1, 3, 2, 1]
    >>> quicksort(li, 0, 5)
    >>> li
    [1, 1, 2, 2, 3, 3]
    """
    if p < r:
        q = partition(li, p, r)
        quicksort(li, p, q-1)
        quicksort(li, q+1, r)


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_min_pos(i, j):
        start = i
        elems = []
        mincost = 10001

        while j != start:
            elems.append((i, j))
            mincost = min(mincost, li1[j])
            i = j
            j = li2.index(li1[j])

        while True:
            (i, j) = elems.pop()
            if li1[j] == mincost:
                elems.append((i, j))
                break

        return reversed(elems)

    def move(i, j):
        cost = 0
        for p, q in find_min_pos(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]:
            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[:]
    quicksort(sli, 0, len(li)-1)

    print(min_cost(li, sli))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
def partition(li, p, r):
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1
    for j in range(p, r):
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

    i += 1
    li[i], li[r] = li[r], li[i]

    return i


def quicksort(li, p, r):
    """sort li by quick sort algorithm.

    >>> li = [3, 2, 1, 3, 2, 1]
    >>> quicksort(li, 0, 5)
    >>> li
    [1, 1, 2, 2, 3, 3]
    """
    if p < r:
        q = partition(li, p, r)
        quicksort(li, p, q-1)
        quicksort(li, q+1, r)


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) * (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
    mini = li1.index(li2[0])

    for i in reversed(range(size)):
        if li1[i] != li2[i]:
            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[:]
    quicksort(sli, 0, len(li)-1)

    print(min_cost(li, sli))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
def partition(li, p, r):
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1
    for j in range(p, r):
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

    i += 1
    li[i], li[r] = li[r], li[i]

    return i


def quicksort(li, p, r):
    """sort li by quick sort algorithm.

    >>> li = [3, 2, 1, 3, 2, 1]
    >>> quicksort(li, 0, 5)
    >>> li
    [1, 1, 2, 2, 3, 3]
    """
    if p < r:
        q = partition(li, p, r)
        quicksort(li, p, q-1)
        quicksort(li, q+1, r)


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
    mini = li1.index(li2[0])

    for i in reversed(range(size)):
        if li1[i] != li2[i]:
            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[:]
    quicksort(sli, 0, len(li)-1)

    print(min_cost(li, sli))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

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
print(loop)
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: Wrong Answer

Solution code:
n = int(input())
loads = list(map(int, input().split()))
min_value = 0
for i in range(n-1):
    tmp = (i,i)
    min = 2 * 10e4 + 1
    for j in range(i,n):
        if loads[i] > loads[j]:
            sum = loads[i] + loads[j]
            if min > sum:
                tmp = (i, j)
                min = sum
    if(min < 2*10e4 + 1):
        min_value += min
    loads[tmp[0]], loads[tmp[1]] = loads[tmp[1]], loads[tmp[0]]

print(min_value)

Submission status: Wrong Answer

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-2) * minc , cirSum + minc + (n+1)*minA)
    a.append(circle)
    

print(total)

Submission status: Time Limit Exceeded

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from itertools import product
from math import inf
from sys import setrecursionlimit

setrecursionlimit(10000)

ws = []
min_weight = inf


def swap(w, i, j):
    tmp = w[i]
    w[i] = w[j]
    w[j] = tmp


def try_next(w, total, hand):
    global min_weight

    if total > min_weight:
        return

    if w == ws:
        min_weight = min(total, min_weight)
        return

    for i, j in product(range(len(w)), range(len(w))):
        if i >= j:
            continue
        wnew = w[:]
        swap(wnew, i, j)
        hnew = hand[:]
        hnew.append((i, j))
        try_next(wnew, total + w[i] + w[j], hnew)

    return


def first_try(w):
    global ws

    weight = 0
    for i in reversed(range(len(w))):
        j = w.index(ws[i])
        if i != j:
            weight += w[i] + w[j]
            swap(w, i, j)
    return weight


def main():
    global ws, min_weight

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

    min_weight = first_try(w[:])
    try_next(w, 0, [])
    print(min_weight)


main()

Submission status: Time Limit Exceeded

Solution code:
w=0
n=input()
A=map(int,raw_input().split())
j=-1
B=list(A)
B.sort()
for i in B:
    j+=1
    if i==max(A):
        break
    while 1:
        if i==A[j]:
            break
        else :
            k=A.index(i)
            w+=i+A[A.index(B[k])]
            A[k]=A[A.index(B[k])]
            A[A.index(B[k])]=i
print(w)

Submission status: Time Limit Exceeded

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 j, bj in enumerate(B):
        t = 0
        i = A.index(bj)
        tmp_cost = 0
        
        # swap in a cyclic group
        while j != i:
            t += 1
            bi = B[i]
            k = A.index(bi)
            tmp_cost += bi + bj #= ak + ai
            swap(A,j,k)
            j = k
        
        # diff. to swap with min(B)
        dec = t * (bj - B[0])
        inc = 2 * (bj + 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: Memory Limit Exceeded

Solution code:
from heapq import heappush, heappop

cache = {}


def remaining_expected_cost(a):
    global n, b, cache
    key = tuple(i for i in range(n) if a[i] != b[i])
    if key in cache:
        return cache[key]
    return sum(a[i] for i in key)


def stack(node):
    global heap, n
    for i in range(n - 1):
        for j in range(i + 1, n):
            swapped = (i, j)
            if swapped == node[2]:
                continue
            a = node[3][:]
            w1, w2 = a[i], a[j] = a[j], a[i]
            spent_cost = node[1] + w1 + w2
            rec = remaining_expected_cost(a)
            if not rec:
                return spent_cost
            heappush(heap, (spent_cost + rec, spent_cost, swapped, a))
    return False


n, a = int(input()), list(map(int, input().split()))
b, m, heap = sorted(a), 0, []

heappush(heap, (remaining_expected_cost(a), 0, None, a))

while heap:
    r = stack(heappop(heap))
    if r is not False:
        m = r
        break
print(m)

Submission status: Accepted

Solution code:
def calcurate_cost(A, B, n):
    cost = 0
    s = min(A)
    V = [False] * n
    T = { j:i for i, j in enumerate(B) }
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = 0
        an = 0
        m = 10000
        while True:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
            if V[cur]:
                break
        cost += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return cost
    
def minimum_cost_sort(A, n):
    B = sorted(A)
    return calcurate_cost(A, B, n)

n = int(input())
A = [int(i) for i in input().split()]
print(minimum_cost_sort(A, 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-1):
    t = cnt = 0
    #本来i番目にいるべき値はaではどこにいるのか（ループの最小値）
    x = a.index(b[i])
    #もしあるべき場所にあったり、あるべき場所に帰ってきたら終了
    while x != i:
        #ループで最も小さい値を使いまわしながら整えていく
        #ループの最小値が入っている場所にいるべき値がaでは何処にいるか
        y = a.index(b[x])
        #a[x]とa[y]を入れ替えればよい
        a[x],a[y] = a[y],a[x];cnt += 1
        t += a[x] + a[y]
        x = y
    if cnt: c += min(t, (b[i]+b[0])*2 + t -(b[i]-b[0])*cnt)
print(c)
# print(a)

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] = a[y],a[x];cnt += 1
        t += a[x] + a[y]
        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=input()
l=map(int,raw_input().split())
s=sorted(l)
c=0
for i in range(n):
    a=l.index(s[i])
    j=0
    while a>i:
        j+=1
        b=l.index(s[a])
        c+=l[b]
        l[a],l[b]=l[b],l[a]
        a=b
    c+=min(s[i]*j,s[i]*2+s[0]*(j+2))
print c

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:
N = int(raw_input())
W = map(int, raw_input().split())
T = sorted(W)
move = {}
for x in W:
    index = T.index(x)
    if x != W[index]:
        move[x] = W[index]

cycle = []
while len(move) > 0:
    l = []
    k, v = move.popitem()
    l.append(k)
    nk = v
    while nk != k:
        nv = move[nk]
        del move[nk]
        l.append(nk)
        nk = nv
    cycle.append(l)
cost = 0
for l in cycle:
    n = len(l)
    minCost = sum(l) + (n-2) * min(l)
    otherCost = sum(l) + min(l) + (n+1) * min(W)
    cost += minCost if minCost < otherCost else otherCost
print cost

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:
def perfect_swap():
    global n, a, b, cost
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            ai, aj = a[i], a[j]
            if ai == b[j] and aj == b[i]:
                a[i], a[j] = aj, ai
                cost += ai + aj


def lowest_swap():
    global n, a, b, cost
    for i in range(n - 1):
        bi, tmp_cost, count = b[i], 0, 0
        while a[i] != bi:
            si = a.index(bi)
            bsi = b[si]
            sj = a.index(bsi)
            a[si], a[sj] = bsi, bi
            tmp_cost += bi + bsi
            count += 1
        if count:
            if i:
                b0 = b[0]
                cost += min(tmp_cost, (bi + b0) * 2 + tmp_cost - (bi - b0) * count)
            else:
                cost += tmp_cost


n, a, cost = int(input()), list(map(int, input().split())), 0
b = sorted(a)
perfect_swap()
lowest_swap()
print(cost)

Submission status: Accepted

Solution code:
n, a, cost = int(input()), list(map(int, input().split())), 0
b = sorted(a)
b0 = b[0]
for i in range(n - 1):
    bi, tmp_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
        tmp_cost += bi + bsi
        count += 1
        si = sj
    if count:
        cost += min(tmp_cost, (bi + b0) * 2 + tmp_cost - (bi - b0) * count)
print(cost)

Submission status: Accepted

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

#weights: list
def minimam_cost_sort(weights):
    mw = min(weights)
    s_w = sorted(weights)
    lol = []
    for i in range(len(weights)):
        if weights[i] != 0:
            j = weights[i]
            idx = s_w.index(j)
            weights[i] = 0
            l = [j]
            while weights[idx] != 0:
                l.append(weights[idx])
                j = weights[idx]
                weights[idx] = 0
                idx = s_w.index(j)
            l.sort()
            lol.append(l)

    lol.sort()
    s = 0
    for l in lol:
        s += get_wol(l, mw)

    print s

def get_wol(l, mw):
    sub = (l[0] - mw) * (len(l) - 1) - (l[0] + mw) * 2
    s = sum(l) + (l[0] * (len(l) - 2))
    if sub > 0:
        return s - sub
    return s

minimam_cost_sort(get_weights())