Algoogle

Algorithm for Programming Contest

AOJ 2361 Sort

Category: AOJ Tag: dijkstra

Sort

問題概要


解法


ソートされた状態から各状態までの最小コストをダイクストラで求めて, その中で最大のものを求める.

コード


(2361.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define repit(i,a) for(__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
typedef vector<int> vi;
typedef pair<int,int> pii;

int vtoi(vi &v){
    int ret = 0;
    rep(i,v.size()){
        ret *= 10;
        ret += v[i];
    }
    return ret;
}

void itov(int n, vi &v){
    int t = v.size();
    rep(i,t){
        v[t-i-1] = n%10;
        n/=10;
    }
}

int main(){
    int n;
    cin >> n;
    vector<vi> cost(n,vi(n));
    rep(i,n)rep(j,n) cin >> cost[i][j];
    vi v(n);
    rep(i,n) v[i] = i;
    int num = vtoi(v);
    priority_queue<pii> que;
    map<int,int> d;
    que.push(pii(num,0));
    d[num] = 0;
    while(!que.empty()){
        num = que.top().first;
        int dist = -que.top().second;
        que.pop();
        if(dist > d[num]) continue;
        vi tmp(n);
        rep(i,n)repi(j,i+1,n){
            itov(num,tmp);
            swap(tmp[i],tmp[j]);
            int t = vtoi(tmp);
            int cst = cost[tmp[i]][tmp[j]];
            map<int,int>::iterator itr = d.find(t);
            if(itr == d.end() || (*itr).second > dist + cst){
                d[t] = dist + cst;
                que.push(pii(t,-dist-cst));
            }
        }
    }
    int ans = 0;
    repit(itr,d) ans = max(ans,(*itr).second);
    cout << ans << endl;
    return 0;
}

Comments