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:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

N = input()
A_ = map(int, raw_input().split())
minA = min(A_)
lst = []
for i in range(N):
    lst.append((A_[i], i))
lst.sort()

A = [0] * N
for i in range(N):
    A[lst[i][1]] = (lst[i][0], i)

flag = [False] * N

def func(pos, lst):
    if flag[pos]:
        return
    lst.append(A[pos][0])
    flag[pos] = True
    func(A[pos][1], lst)

ans = 0
for i in range(N):
    if not flag[i]:
        ret = []
        func(i, ret)
        ans += min(min(ret) * (len(ret) - 2) + sum(ret), sum(ret) + min(ret) + minA * (len(ret) + 1))

print ans

Submission status: Runtime Error

Solution code:
def get_weights():
    input()
    return raw_input().split()

#weights: list
def minimam_cost_sort(weights):
    lol = []
    for i in weights:
        if i !=0:
            j = i
            l = [j]
            while weights[j - 1] != 0:
                l.append(weights[j - 1])
                j = weights[j - 1]
                weights[j - 1] = 0
            l.sort()
            lol.append(l)

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

    print s

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

minimam_cost_sort(get_weights())

Submission status: Runtime Error

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

#weights: list
def minimam_cost_sort(weights):
    lol = []
    for i in range(len(weights)):
        if weights[i] !=0:
            j = weights[i]
            weights[i] = 0
            l = [j]
            while weights[j - 1] != 0:
                l.append(weights[j - 1])
                k = j
                j = weights[k - 1]
                weights[k - 1] = 0
            l.sort()
            lol.append(l)

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

    print s

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

minimam_cost_sort(get_weights())

Submission status: Runtime Error

Solution code:
import sys

def minimumCostSort(A):
    B = sorted(A)
    V = [False] * len(A)
    T = [0] * 10000
    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: Runtime Error

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)
    #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 = [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: Runtime Error

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

import sys

MAX_VALUE = 1e4


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] * (array_length + 1)
    compare_ans = sorted(array)
    for j in range(array_length):
        kv_reverse[compare_ans[j]] = j
    print(min_cost_sort())

Submission status: Runtime Error

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 * (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: Runtime Error

Solution code:
# line = "4 3 2 1"
# 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 = []

for i, x in enumerate(L):
    k = x - 1
    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 = x - 1
    loops.append(loop)

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

print(cost)

Submission status: Runtime Error

Solution code:
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 x not in loop:
        flags[k] = True
        loop.append(x)
        x = L[k]
        k = x - 1
    loops.append(loop)

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

print(cost)

Submission status: Runtime Error

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)}
	T = {B: i for i, B in enumerate(sorted(A))}
    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: Runtime Error

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[b]
  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: Runtime Error

Solution code:
let quick_sort a n cmp =
  let swap i j = let tmp = a.(i) in a.(i) <- a.(j); a.(j) <- tmp in
  let partition p r =
    let i = ref p in
    for j = p to r - 1 do
      if cmp a.(j) a.(r) <= 0 then (swap !i j; incr i)
    done;
    swap !i r;
    !i in
  let rec doit p r =
    if p >= r then () else
    let q = partition p r in
    doit p (q - 1);
    doit (q + 1) r in
  doit 0 (n - 1)

let calc_cost a n =
  let b = Array.copy a in
  quick_sort b n compare;
  let t = Array.make (b.(n-1) + 1) 0 in
  Array.iteri (fun i e -> t.(e) <- i) b;
  let p = Array.make n false in
  let rec cycle i acc =
    p.(i) <- true;
    let j = t.(a.(i)) in
    if p.(j) then a.(i) :: acc
    else cycle j (a.(i) :: acc) in
  let cycle i = cycle i [] in
  let rec doit i acc =
    if i = n then acc
    else if p.(i) then doit (i + 1) acc
    else
      let ws = cycle i in
      let m = List.length ws in
      let s = List.fold_left (+) 0 ws in
      let z = List.fold_left min max_int ws in
      doit (i + 1) (acc + (min (s + (m - 2)*z) (s + z + (m + 1)*b.(0)))) in
  doit 0 0

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> Scanf.scanf "%d " (fun e -> e)) in
  calc_cost a n |> Printf.printf "%d\n"

Submission status: Runtime Error

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

    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[:]
    quicksort(sli, 0, len(li)-1)

    print(min_cost(li, sli))


if __name__ == '__main__':
    run()

Submission status: Runtime Error

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


def quick_sort(a, p, r):
    if p < r:
        q = partition(a, p, r)
        quick_sort(a, p, q-1)
        quick_sort(a, q+1, r)


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()
    quick_sort(v, 0, len(v) - 1)

    cyclics = make_cyclic(w, v)

    ans = 0
    for cycle in cyclics:
        inner_cycle = min(cycle) * (len(cycle) - 2) + sum(cycle)
        outer_cycle = min(cycle) + min(set(w) - set(cycle)) * (len(cycle) + 1) + sum(cycle)
        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: Runtime Error

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


def quick_sort(a, p, r):
    if p < r:
        q = partition(a, p, r)
        quick_sort(a, p, q-1)
        quick_sort(a, q+1, r)


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()
    quick_sort(v, 0, len(v) - 1)

    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))