V8SORT - Sắp xếp
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<iostream>
#include<map>
#include<queue>
#include<sstream>
#include<string>
#include<vector>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi first
#define se second
using namespace std;
const int INF=(int)1e9+7;
typedef pair<int,vector<int> > State;
map<vector<int>,int> dis;
vector<int> sta;
int cost[11][11];
int n;
void init(void) {
string inp;
getline(cin,inp);
stringstream ss(inp);
int x;
while (ss>>x) sta.push_back(x);
n=sta.size();
REP(i,n) REP(j,n) cin>>cost[i][j];
}
bool isEnd(const vector<int> &v) {
REP(i,(int)v.size()-1) if (v[i]>v[i+1]) return (false);
return (true);
}
int getDis(const vector<int> &v) {
return (dis.find(v)==dis.end()?INF:dis[v]);
}
void dijkstra(void) {
priority_queue<State,vector<State>,greater<State> > q;
dis[sta]=0;
q.push(State(0,sta));
while (!q.empty()) {
int d=q.top().fi;
vector<int> cur=q.top().se;
q.pop();
if (d!=getDis(cur)) continue;
if (isEnd(cur)) {
printf("%d\n",d);
return;
}
REP(i,n) REP(j,n) if (i<j) {
swap(cur[i],cur[j]);
if (getDis(cur)>d+cost[i][j]) {
dis[cur]=d+cost[i][j];
q.push(State(d+cost[i][j],cur));
}
swap(cur[i],cur[j]);
}
}
}
int main(void) {
init();
dijkstra();
return 0;
}