AOJ 1108 - A Long Ride on a Railway

問題概要

V個の駅とE本の区間があり、駅には1からVの番号が与えられている。E本の区間には距離が与えられており、その距離の総和を最大化せよ。ただし、同じ区間は1度しか訪れることができない。さらに最大距離の中で経路が辞書順最小になるようにせよ。

制約

• 1 ≤ V ≤ 10
• 1 ≤ E ≤ 20

解法

dfsで全探索。
制約が小さいので余裕で間に合う。
また、dfsをすることではじめに訪れた最大距離が経路の辞書順最小になる。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 10
 
struct Edge{
  int dst,weight;
  Edge(int dst,int weight) : dst(dst),weight(weight) {}
};
 
int V,E;
int ans_dist;
vector<int> ans;
vector<Edge> G[MAX];
bool visited[MAX][MAX];
 
void dfs(int v,int dist,vector<int> &routes){
  if(ans_dist < dist){
    ans_dist = dist;
    ans = routes;
  }
  for(int i = 0 ; i < (int)G[v].size() ; i++){
    int to = G[v][i].dst;
    if(visited[v][to]) continue;
    visited[v][to] = visited[to][v] = true;
    routes.push_back(to+1);
    dfs(to,dist+G[v][i].weight,routes);
    routes.pop_back();
    visited[v][to] = visited[to][v] = false;
  }
}
 
int main(){
  int a,b,c;
  while(cin >> V >> E, (V | E)){
    ans_dist = 0; ans.clear();
    for(int i = 0 ; i < V ; i++){
      G[i].clear();
    }
    memset(visited,false,sizeof(visited));
    for(int i = 0 ; i < E ; i++){
      cin >> a >> b >> c; a--, b--;
      G[a].push_back(Edge(b,c));
      G[b].push_back(Edge(a,c));
    }
    vector<int> vec;
    for(int i = 0 ; i < V ; i++){
      vec.push_back(i+1);
      dfs(i,0,vec);
      vec.pop_back();
    }
    cout << ans_dist << endl;
    for(int i = 0 ; i < (int)ans.size() ; i++){
      if(i) cout << " ";
      cout << ans[i];
    }
    cout << endl;
  }
  return 0;
}