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; }