旅行コース

コード#コード#

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<string>> ansList;
vector<string> ans;
void DFS(int depth, string prevDest, bool* isused, vector<vector<string>>& tickets){
    if(depth == tickets.size())
    {
        ans[depth] = prevDest;
        vector<string> tmp;
        for(int i=0;i<=depth;i++) tmp.push_back(ans[i]);    
        ansList.push_back(tmp);
        return;
    }else{
        for(int i=0;i<tickets.size();i++)
        {
            if(isused[i]) continue;
            if(tickets[i][0] != prevDest) continue;
            isused[i] = true;
            ans[depth] = tickets[i][0];
            DFS(depth+1, tickets[i][1], isused, tickets);
            isused[i] = false;
        }
    }
}
vector<string> solution(vector<vector<string>> tickets) {
    ans.resize(10000);
    bool isused[tickets.size()];
    fill(isused, isused+tickets.size(), false);
    for(int i=0;i<tickets.size();i++)
    {
        if(tickets[i][0] != "ICN") continue;
        isused[i] = true;
        ans[0] = tickets[i][0];
        DFS(1, tickets[i][1], isused, tickets);
        isused[i] = false;
    }
    stable_sort(ansList.begin(), ansList.end());
    return ansList[0];
}