UVa11813 Shopping

問題
http://uva.onlinejudge.org/external/118/11813.html

概要
無向グラフにおいて、グラフの接続情報とコストが与えられる。
全てのノードの内、店のノード番号が複数指定されるので、ノード0から出発して最小コストで全ての店を巡回せよ。

制約

ノードとエッジの数はそれぞれ 100000 以下
店は10店舗以下。

解法
すべての店からダイクストラした後、TSPを解く。
高々11回(店舗数+はじめの位置)のダイクストラをすれば良い。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX_V (100010)
#define INF ((int)1e9)

struct Edge {
  int to, cost;
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

Graph G;

int N, M, S;
int stores[11];
int d[11][MAX_V];

typedef pair<int, int> Pii; // cost, curr
void dijkstra(int sid) {
  
  fill(d[sid], d[sid]+MAX_V, INF);
  d[sid][stores[sid]] = 0;
  priority_queue<Pii, vector<Pii>, greater<Pii> > pq;
  pq.push(Pii(0, stores[sid]));
  while(!pq.empty()) {
    Pii top = pq.top(); pq.pop();
    int const curr = top.second;
    int const cost = top.first;
    for(int i=0; i<G[curr].size(); i++) {
      const Edge& e = G[curr][i];
      if(d[sid][e.to] > cost+e.cost) {
        d[sid][e.to] = cost+e.cost;
        pq.push(Pii(cost+e.cost, e.to));
      }
    }
  }
  
}

int dp[1<<11][11];
int main() {
  
  int Tc; cin >> Tc;
  while(Tc--) {
    cin >> N >> M;
    G.clear(); G.resize(N);
    for(int i=0; i<M; i++) {
      int x, y, c; cin >> x >> y >> c;
      G[x].push_back((Edge){y, c});
      G[y].push_back((Edge){x, c});
    }
    
    cin >> S; stores[0] = 0; S++;
    for(int i=1; i<S; i++) {
      int x; cin >> stores[i];
    }
    for(int i=0; i<S; i++)
      dijkstra(i);
    
    fill(dp[0], dp[0]+(1<<11)*11, INF);
    dp[1][0] = 0;
    for(int st=0; st<(1<<S); st++) {
      for(int u=0; u<S; u++) {
        if(!((st>>u)&1)) continue;
        for(int v=0; v<S; v++) {
          if((st>>v)&1) continue;
          if(dp[st|(1<<v)][v] > dp[st][u]+d[u][stores[v]]) {
            dp[st|(1<<v)][v] = dp[st][u]+d[u][stores[v]];
          }
        }
      }
    }
    
    int ans = INF;
    for(int i=1; i<S; i++) {
      ans = min(ans, dp[(1<<S)-1][i]+d[i][stores[0]]);
    }
    
    cout << ans << endl;
    
  }
  
  return 0;
}