LEM3 spoj - TRIP - Kiến Thức 24h

Nguồn đề bài: http://vn.spoj.com/problems/LEM3/

1. Đề bài LEM3 spoj

Trong kì nghỉ hè năm nay sherry được bố thưởng cho 1 tour du lịch quanh N đất nước tươi đẹp với nhiều thắng cảnh nổi tiếng ( vì sherry rất ngoan ). Tất nhiên sherry sẽ đi bằng máy bay.

Giá vé máy bay từ đất nước i đến đất nước j là C_ij ( dĩ nhiên C_ij có thể khác C_ji ). Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng sherry cũng muốn tìm cho mình 1 hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặng mọi người ( Các chuyến bay của sherry đều được đảm bảo an toàn tuyệt đối ).

Bạn hãy giúp sherry tìm 1 hành trình đi qua tất cả các nước, mỗi nước đúng 1 lần sao cho chi phí là bé nhất nhé.

Input

Dòng 1: N (5 < N < 16)

Dòng thứ i trong N dòng tiếp theo: Gồm N số nguyên, số thứ j là C_ij (0 < C_ij < 10001)

Output

Gồm 1 dòng duy nhất ghi chi phí bé nhất tìm được

Example

Input:
6
0 1 2 1 3 4
5 0 3 2 3 4
4 1 0 2 1 2
4 2 5 0 4 3
2 5 3 5 0 2
5 4 3 3 1 0


Output:
8

2. Hướng dẫn LEM3 spoj

Bài này sử dụng BIT và BFS:

Dùng một dãy bit để biểu diễn cách đi của Sherry.

Gọi kc[i][k] là khoảng cách min để sherry đi qua các nước đã được biểu diễn bằng bit 1 trong i và nước cuối cùng đi qua là k.

BFS trên đồ thị có các đỉnh là một cặp số (i,k) (với i, k như trên)

từ một đỉnh (i,k) có thể đi tới đỉnh (i1,k1) với điều kiện:

Đỉnh k1 được biểu diễn với bit 0 trong i. Khi đó ta có công thức:

kc[i1][k1]=kc[i][k]+c[k][k1];

Mình nói hơi khó hiểu. h mk sẽ share code. Nếu có thắc mắc, các bạn có thể đăng nhập và cmt, mk sẽ giải thích. Cảm ơn! 😀

3. Code mẫu LEM3 spoj

#include <bits/stdc++.h>
#define oo 1000000000;
using namespace std;
typedef pair<int,int> II;
    int n,u,v,k,c[17][17],cl[1000000][17],kc[1000000][17];
    II q[1000000];
void loang()
{
    for(int i=1; i<(1<<n); i++)
        for(int j=0; j<=n; j++)
    {
        kc[i][j]=oo;
        cl[i][j]=0;
    }
    int l=1, r=0;
    q[++r]=II(0,0); cl[0][0]=1; kc[0][0]=0;
    while(l<=r)
    {
        II t=q[l++];
        u=t.first, k=t.second;
        for(int i=1; i<=n; i++)
        {
            if((u&(1<<(i-1)))==0)
            {
                v=u|(1<<(i-1));
                kc[v][i]=min(kc[v][i],kc[u][k]+c[k][i]);
                if(cl[v][i]==0)
                {
                    cl[v][i]=1;
                    q[++r]=II(v,i);
                }
            }
        }
    }
    int ds=oo;
    for(int i=1; i<=n; i++)
        ds=min(ds,kc[(1<<n)-1][i]);
    cout<<ds;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        cin>>c[i][j];
    loang();
}

LEM3 spoj – TRIP