solution.md

# 重新安排行程

<p>给你一份航线列表 <code>tickets</code> ，其中 <code>tickets[i] = [from<sub>i</sub>, to<sub>i</sub>]</code> 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。</p>

<p>所有这些机票都属于一个从 <code>JFK</code>（肯尼迪国际机场）出发的先生，所以该行程必须从 <code>JFK</code> 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。</p>

<ul>
	<li>例如，行程 <code>["JFK", "LGA"]</code> 与 <code>["JFK", "LGB"]</code> 相比就更小，排序更靠前。</li>
</ul>

<p>假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。</p>



<p><strong>示例 1：</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/14/itinerary1-graph.jpg" style="width: 382px; height: 222px;" />
<pre>
<strong>输入：</strong>tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

<strong>输出：</strong>["JFK","MUC","LHR","SFO","SJC"]
</pre>

<p><strong>示例 2：</strong></p>

<img alt="" src="https://assets.leetcode.com/uploads/2021/03/14/itinerary2-graph.jpg" style="width: 222px; height: 230px;" />
<pre>
<strong>输入：</strong>tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

<strong>输出：</strong>["JFK","ATL","JFK","SFO","ATL","SFO"]

<strong>解释：</strong>另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
</pre>



<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= tickets.length <= 300</code></li>
	<li><code>tickets[i].length == 2</code></li>
	<li><code>from<sub>i</sub>.length == 3</code></li>
	<li><code>to<sub>i</sub>.length == 3</code></li>
	<li><code>from<sub>i</sub></code> 和 <code>to<sub>i</sub></code> 由大写英文字母组成</li>
	<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>
</ul>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
unordered_map<int, string> rev;
int cmp(pair<int, int> x, pair<int, int> y)
{
    return rev[x.first] < rev[y.first];
}
class Solution
{
public:
    unordered_map<string, int> mp;
    int cnt = 0;
    int head[10005], nex[10005], to[10005], tot = 0;
    int vis[10005];
    vector<string> ans;
    void add(int x, int y)
    {
        to[++tot] = y;
        nex[tot] = head[x];
        head[x] = tot;
    }

    void euler(int x)
    {
        vector<pair<int, int>> vec;
        for (int i = head[x]; i; i = nex[i])
        {
            int v = to[i];
            if (vis[i])
            {
                continue;
            }
            vec.push_back({v, i});
        }
        sort(vec.begin(), vec.end(), cmp);
        for (int i = 0; i < vec.size(); i++)
        {
            if (vis[vec[i].second])
                continue;
            vis[vec[i].second] = 1;
            euler(vec[i].first);
            ans.push_back(rev[vec[i].first]);
        }
    }
    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        mp["JFK"] = 1;
        rev[1] = "JFK";
        cnt = 1;
        for (int i = 0; i < tickets.size(); i++)
        {
            string s1 = tickets[i][0], s2 = tickets[i][1];
            if (mp[s1])
            {
                mp[s1] = ++cnt;
                rev[cnt] = s1;
            }
            if (mp[s2])
            {
                mp[s2] = ++cnt;
                rev[cnt] = s2;
            }
            add(mp[s1], mp[s2]);
        }
        euler(1);
        ans.push_back(rev[1]);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

```
## 选项


### A

```c
class Solution
{

public:
    vector<string> ans;
    unordered_map<string, vector<string>> ticket;
    unordered_map<string, vector<int>> use;
    bool dfs(string &now, int begin, int n)
    {
        if (begin == n)
        {
            return true;
        }
        else
        {
            int size = ticket[now].size();
            for (int i = 0; i < size; i++)
            {
                if (!use[now][i])
                {
                    ans.push_back(ticket[now][i]);
                    use[now][i] = 1;
                    if (dfs(ticket[now][i], begin + 1, n))
                        return true;
                    ans.pop_back();
                    use[now][i] = 0;
                }
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        int n = tickets.size();
        for (int i = 0; i < n; i++)
        {
            int j, n = ticket[tickets[i][0]].size();
            for (j = 0; j < n; j++)
                if (ticket[tickets[i][0]][j] >= tickets[i][1])
                    break;
            ticket[tickets[i][0]].insert(ticket[tickets[i][0]].begin() + j, tickets[i][1]);
            use[tickets[i][0]].push_back(0);
        }
        string beginC = "JFK";
        ans.push_back(beginC);
        dfs(beginC, 0, n);
        return ans;
    }
};
```

### B

```c
class Solution
{
    unordered_map<string, multiset<string>> m;
    vector<string> ans;

public:
    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        for (auto &t : tickets)
            m[t[0]].insert(t[1]);
        dfs("JFK");
        reverse(ans.begin(), ans.end());
        return ans;
    }
    void dfs(string s)
    {
        while (m[s].size() != 0)
        {
            string to = *m[s].begin();
            m[s].erase(m[s].begin());
            dfs(to);
        }
        ans.push_back(s);
    }
};
```

### C

```c
class Solution
{
public:
    struct cmp
    {
        bool operator()(const string &a, const string &b)
        {
            return a > b;
        }
    };

    vector<string> findItinerary(vector<pair<string, string>> tickets)
    {
        map<string, int> m;
        vector<priority_queue<string, vector<string>, cmp>> queues;
        for (auto p : tickets)
        {
            if (m.find(p.first) == m.end())
            {
                priority_queue<string, vector<string>, cmp> newQueue;
                newQueue.push(p.second);
                queues.push_back(newQueue);
                m.insert(make_pair(p.first, queues.size() - 1));
            }
            else
            {
                queues[m[p.first]].push(p.second);
            }
        }

        vector<string> ans;
        stack<string> visitedPlaces;
        visitedPlaces.push("JFK");

        while (!visitedPlaces.empty())
        {
            string current = visitedPlaces.top();
            if (m.find(current) == m.end() || queues[m[current]].size() == 0)
            {
                ans.push_back(current);
                visitedPlaces.pop();
            }
            else
            {
                visitedPlaces.push(queues[m[current]].top());
                queues[m[current]].pop();
            }
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};
```