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;
}

Download