Minimum Cost Sort
Time Limit : 1 sec, Memory Limit : 131072 KB Japanese version is here
Minimum Cost Sort
You are given nn integers wi(i=0,1,...,n−1)wi(i=0,1,...,n−1) to be sorted in ascending order. You can swap two integers wiwi and wjwj. Each swap operation has a cost, which is the sum of the two integers wi+wjwi+wj. 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 nn is given. In the second line, nn integers wi(i=0,1,2,...n−1)wi(i=0,1,2,...n−1) separated by space characters are given.
Output
Print the minimal cost in a line.
Constraints
1≤n≤1,0001≤n≤1,0000≤wi≤1040≤wi≤104wiwi 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
Source: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_6_D
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define clr(a) memset(a,b,sizeof(a))
#define il inline
#define reg register
#define rep(i,a,n) for(reg int i=a;i<n;i++)
typedef long long ll;
const int maxn=10000+5;
const int minn=1000+5;
const int inf=2e9+2;
int n,a[minn],po[maxn];
void solve()
{
sort(a+1,a+n+1);
int f=0,tp=inf,t=0,tmin=a[1];
ll w=0,ans=0;
rep(i,1,n+1)
{
if(po[a[i]]==i){continue;}
tp=inf;t=1;w=0;
int f=po[a[i]];
w+=a[i];
tp=a[i];
while(f!=i)
{
t++;tp=min(a[f],tp);
w+=a[f];
int tm=f;
f=po[a[f]];
po[a[tm]]=tm;
}
ans+=min(w+(t-2)*tp,w+tp+(t+1)*tmin);
}
printf("%lld\n",ans);
}
int main()
{
scanf("%d",&n);
rep(i,1,n+1)
{
scanf("%d",&a[i]);
po[a[i]]=i;
}
solve();
return 0;
}
