# TIOJ 1028 . 旅遊規劃問題（位元DP）

### 題目連結：https://tioj.ck.tp.edu.tw/problems/1028

****
### 解題想法：
>DP[ i ][ j ]，i 為目前位置的編號，j 為還沒走過的點集，因為數量很少，可以以[bit mask](https://codeforces.com/blog/entry/18169)表示，對於每一種狀態，用[Dijkstra](https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/)求出每一個沒走過的點（不在這個狀態中）到這個狀態的最短距離，轉移式為
>
>DP[ i ][ j ] = 對於每個在 $j$ 中的 $x$ -> DP[ $x$ ][ $j$ ^ ($1$<<$x$) ] + ( i 到 x 的最短距離 ) 的最小值

### Dijkstra實作（每個狀態做一次）：

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define F first
#define S second
#define INF (ll)1e17

    struct Q{

        int id;

        ll dis;

        bool operator<(const Q& rhs)const{

            return dis>rhs.dis;

        }
        
    }; // 通過重載運算子，自訂 priority_queue 比較函式
        
        vector<int> e[15]; // 每個點連到的點

        ll d[15]; // 每個點到這個狀態的最短距離
        
        int num[15][(1<<n)]; // 記錄最後要輸出的答案，即每個點在每個狀態中的下一個點是誰
        
        bool done[15]; // 記錄每個點是否已經找到最短距離
        
        fill(d,d+15,INF); // 初始為INF
        
        memset(done,0,sizeof(done)); // 初始為未找到
        
        priority_queue<Q> pq;
        
        FOR(j,0,n)if(i&(1<<j)){
        
            d[j]=dp[j][i^(1<<j)]; // 若已在此狀態中，將距離設為上一狀態
            
            pq.push((Q){j,d[j]}); // 放入priority_queue
            
        }
        
        while(!pq.empty()){
            
            auto now=pq.top(); pq.pop();
            
            if(done[now.id]) continue; // 若已做過便不需再做一次
            
            done[now.id]=1; // 標記為已做過
            
            for(auto x:e[now.id])if(!(i&(1<<x.F))){ // 只取不在此狀態中的元素
            
                if(d[x.F]>d[now.id]+x.S){ // 若距離較原本短，就更新
                
                    d[x.F]=d[now.id]+x.S;
                    
                    pq.push((Q){x.F,d[x.F]});
                    
                    num[x.F][i]=now.id;
                }
                
                else if(d[x.F]==d[now.id]+x.S&&num[x.F][i]>now.id){ 
                // 若距離一樣但編號較小，也要更新，因為題目要求答案為字典序最小的
                
                    num[x.F][i]=now.id;
                    
                }
                
            }
            
        }

### 完整程式碼

#include<bits/stdc++.h>

#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define INF (ll)1e17
#define F first
#define S second

using namespace std;

vector<pair<int,int> > e[15];

ll dp[15][1<<14],d[15];

int num[15][(1<<14)];

struct Q{
    int id;
    ll dis;
    bool operator<(const Q& rhs) const{
        return dis>rhs.dis;
    }
};

priority_queue<Q> pq;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    
    FOR(i,0,m){
        int a,b,c;
        cin>>a>>b>>c;
        e[a].push_back({b,c});
        e[b].push_back({a,c});
    }
    
    int k,S=0,x,sta=-1;
    bool done[15];
    cin>>k;
    FOR(i,0,k){
        cin>>x;
        S|=(1<<x);//making Bitmask
        if(sta==-1) sta=x;//起點
    }
    
    FOR(i,0,n)FOR(j,0,n) dp[i][j]=INF;
    FOR(i,0,n) dp[i][0]=0;//全部完成時
    
    FOR(i,1,(1<<n))if(i==(i&S)){
        
        while(!pq.empty()) pq.pop();
        
        fill(d,d+n,INF);memset(done,0,sizeof(done));
        
        FOR(j,0,n)if(i&(1<<j)){
            d[j]=dp[j][i^(1<<j)];
            pq.push((Q){j,d[j]});
        }
        
        while(!pq.empty()){
            
            auto now=pq.top(); pq.pop();
            
            if(done[now.id]) continue;
            done[now.id]=1;
            
            for(auto x:e[now.id])if(!(i&(1<<x.F))){
                if(d[x.F]>d[now.id]+x.S){
                    d[x.F]=d[now.id]+x.S;
                    pq.push((Q){x.F,d[x.F]});
                    num[x.F][i]=now.id;
                }
                else if(d[x.F]==d[now.id]+x.S&&num[x.F][i]>now.id){
                    num[x.F][i]=now.id;
                }
            }
        }
        
        FOR(j,0,n)if(!(i&(1<<j))){
            dp[j][i]=d[j];
        }
    }
    
    cout<<"Minimum travel distance: "<<dp[sta][(S^(1<<sta))]<<endl;
    int now=sta,cnt=0;
    cout<<"Travel route: ";
    while(1){
        cnt++;
        cout<<now<<" ";
        if(S&(1<<now)) S=S^(1<<now);
        now=num[now][S];
        if(S==0) break;
    }
}