読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj DPL_2_B

algorithm algorithm-動的計画法 contest contest-aoj language language-c++11

Chinese Postman Problem | Aizu Online Judge
Spaghetti Source - 無向中国人郵便配達問題

ll chinesePostman(const Graph &g)
{
  ll total = 0;
  vector<int> odds;
  REP(u, g.size())
  {
    for(auto e : g[u]) total += e.cost;
    if (g[u].size() % 2) odds.push_back(u);
  }
  total /= 2;
  int n = odds.size(), N = 1 << n;
  ll w[n][n]; // make odd vertices graph
  REP(u,n) {
    int s = odds[u]; // dijkstra's shortest path
    vector<ll> dist(g.size(), INF); dist[s] = 0;
    vector<int>    prev(g.size(), -2);
    priority_queue<Edge> Q;
    Q.push( Edge(-1, s, 0) );
    while (!Q.empty())
    {
      Edge e = Q.top(); Q.pop();
      if (prev[e.dst] != -2) continue;
      prev[e.dst] = e.src;
      for(auto f : g[e.dst])
      {
        if (dist[f.dst] > e.cost+f.cost)
        {
          dist[f.dst] = e.cost+f.cost;
          Q.push(Edge(f.src, f.dst, e.cost+f.cost));
        }
      }
    }
    REP(v,n) w[u][v] = dist[odds[v]];
  }
  ll best[N]; // DP for general matching
  REP(S,N) best[S] = INF;
  best[0] = 0;

  for (int S = 0; S < N; ++S)
    for (int i = 0; i < n; ++i) if (!(S&(1<<i)))
      for (int j = i+1; j < n; ++j) if (!(S&(1<<j)))
        best[S|(1<<i)|(1<<j)] = min(best[S|(1<<i)|(1<<j)], best[S]+w[i][j]);
  return total + best[N-1];
}

int main()
{
  int n, m; cin >> n >> m;
  Graph g(n);
  REP(i,m)
  {
    int s, t; ll c; cin >> s >> t >> c;
    g[s].push_back(Edge(s,t,c));
    g[t].push_back(Edge(t,s,c));
  }
  cout << chinesePostman(g) << endl;
  return 0;
}