class Solution {
    int n;
public:
    void bfs(const vector<vector<int>> & graph, priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> & pq, vector<int> & distance, vector<int> & visited, const int & node) {
        visited = vector<int>(n, 0);
        pq.emplace(0, node);
        visited[node] = 1;
        distance[node] = 0;

        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            for(const auto & adj: graph[cur]) {
                if(distance[adj] > distance[cur] + 1) {
                    distance[adj] = distance[cur] + 1;
                    pq.emplace(distance[adj], adj);
                }
            }
        }
    }
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        n = edges.size();
        vector<vector<int>> graph(n);
        for(int i = 0; i < n; i++) {
            if(edges[i] == -1) continue;
            graph[i].emplace_back(edges[i]);
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        vector<int> distance1(n, INT_MAX / 2);
        vector<int> distance2(n, INT_MAX / 2);
        vector<int> visited;

        bfs(graph, pq, distance1, visited, node1);
        bfs(graph, pq, distance2, visited, node2);

        // Get the distance. Then check the answer.
        int ans_dist = INT_MAX / 2;
        int ans = -1;

        for(int i = 0; i < n; i++) {
            int tmp_ans = max(distance1[i], distance2[i]);
            if(ans_dist > tmp_ans) {
                ans_dist = tmp_ans;
                ans = i;
            }
            else if(ans_dist == tmp_ans) {
                ans = min(ans, i);
            }
        }
        return ans == INT_MAX / 2 ? -1 : ans;
    }
};

class Graph {
    vector<vector<pair<int,int>>>graph;
    vector<int> visited;
    vector<int> distance;
    int n;
public:
    Graph(int n, vector<vector<int>>& edges) {
        graph = vector<vector<pair<int,int>>>(n);
        for(const auto & edge: edges) {
            int from = edge[0], to = edge[1], edgeCost = edge[2];
            graph[from].emplace_back(to, edgeCost);
        }
        Graph::n = n;
    }
    
    void addEdge(vector<int> edge) {
        int from = edge[0], to = edge[1], edgeCost = edge[2];
        graph[from].emplace_back(to, edgeCost);
    }
    
    int shortestPath(int node1, int node2) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        visited = vector<int>(n, 0);
        distance = vector<int>(n, INT_MAX / 2);
        pq.emplace(0, node1);
        distance[node1] = 0;
        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(visited[cur]) continue;
            visited[cur] = 1;
            for(const auto & adj: graph[cur]) {
                const auto [adj_to, adj_w] = adj;
                if(distance[adj_to] > distance[cur] + adj_w) {
                    distance[adj_to] = distance[cur] + adj_w;
                    pq.emplace(distance[adj_to], adj_to);
                }
            }
        }
        return distance[node2] == INT_MAX / 2 ? -1 : distance[node2];
    }
};

/**
 * Your Graph object will be instantiated and called as such:
 * Graph* obj = new Graph(n, edges);
 * obj->addEdge(edge);
 * int param_2 = obj->shortestPath(node1,node2);
 */

constexpr int directions[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        // [dist, x, y];
        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
        pq.emplace(0, 0, 0);
        int rows = moveTime.size(), cols = moveTime[0].size();
        vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX / 2));
        vector<vector<int>> visited(rows, vector<int>(cols, 0));
        distance[0][0] = 0;

        while(!pq.empty()) {
            const auto [dist, x, y] = pq.top();
            pq.pop();
            if(visited[x][y]) continue;
            visited[x][y] = 1;
            for(int i = 0; i < 4; i++) {
                int nx = x + directions[i][0], ny = y + directions[i][1];
                if(nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                    int temp_distance = max(dist, moveTime[nx][ny]) + (x+y) % 2 + 1;
                    if(temp_distance < distance[nx][ny]) {
                        distance[nx][ny] = temp_distance;
                        pq.emplace(temp_distance, nx, ny);
                    }
                }
            }
        }
        return distance[rows - 1][cols - 1];
    }
};

class Solution {
public:
    int n;
    int CheckTransfer(int nums, vector<vector<int>> & board) {
        int row, col;
        if(nums % n == 0) {
            row = n - nums / n;
            if(row % 2 != n % 2) {
                col = n-1;
            }
            else {
                col = 0;
            }
        } else {
            row = n - 1 - nums / n;
            if(row % 2 != n % 2) {
                col = (nums % n) - 1;
            }
            else {
                col = n - (nums % n);
            }
        }
        
        // // ** debug **
        // cout << nums << " at: (" << row << " ," << col << ")\n";
        return board[row][col]; 
    }
    int snakesAndLadders(vector<vector<int>>& board) {
        // Build Matrix.
        n = board.size();

        vector<int> distance(n*n+1, INT_MAX / 2);
        vector<int> visited(n*n+1, 0);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.emplace(0,1);
        distance[1] = 0;
        while(!pq.empty()) {
            // BFS to get the adjacent point.
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(visited[cur]) continue;
            visited[cur] = 1;
            for(int i = cur + 1; i <= min(cur + 6, n * n); i++) {
                int transfer = CheckTransfer(i, board);
                int adj = transfer == -1 ? i : transfer;
                if(distance[adj] > distance[cur] + 1) {
                    distance[adj] = distance[cur] + 1;
                    pq.emplace(distance[adj], adj);
                }
            }
        }
        return distance[n * n] == INT_MAX / 2 ? -1 : distance[n * n];
    }
};

class Solution {
public:
    int n;
    int CheckTransfer(int nums, vector<vector<int>> & board) {
        int row, col;
        if(nums % n == 0) {
            row = n - nums / n;
            if(row % 2 != n % 2) {
                col = n-1;
            }
            else {
                col = 0;
            }
        } else {
            row = n - 1 - nums / n;
            if(row % 2 != n % 2) {
                col = (nums % n) - 1;
            }
            else {
                col = n - (nums % n);
            }
        }
        
        // // ** debug **
        // cout << nums << " at: (" << row << " ," << col << ")\n";
        return board[row][col]; 
    }
    int snakesAndLadders(vector<vector<int>>& board) {
        // Build Matrix.
        n = board.size();

        vector<int> visited(n*n+1, 0);
        queue<pair<int,int>> q;
        q.emplace(1, 0);
        while(!q.empty()) {
            // BFS to get the adjacent point.
            const auto [cur, dist] = q.front();
            q.pop();
            visited[cur] = 1;
            for(int i = cur + 1; i <= min(cur + 6, n * n); i++) {
                int transfer = CheckTransfer(i, board);
                int adj = transfer == -1 ? i : transfer;
                if(visited[adj]) continue;
                if(adj == n * n) return dist + 1;
                visited[adj] = 1;
                q.emplace(adj, dist + 1);
            }
        }
        return -1;
    }
};

func distributeCandies(n int, limit int) int64 {
	var ans int64
	ans = 0
	for i := 0; i <= min(limit, n); i++ {
		ans = ans + int64(max(int64(min(limit, n-i)) - int64(max(n-i-limit, 0))+1, 0))
	}
	return ans
}

class Solution {
public:
    long long distributeCandies(int n, int limit) {
        long long ans = 0;
        for(int i = 0; i <= min(limit, n); i++) {
            ans += (long long)max(min(limit, n-i) - max(n-i-limit, 0) + 1, 0);
        }
        return ans;
    }
};

CONGA 观察到了 ECMP 在负载均衡方面的缺陷：

• 爆发大流时受限于哈希随机分配，碰撞概率增大导致负载不均衡。
• 仅关注局部信息而未关注到潜在下游通路的拥塞影响。
  导致了链路故障情况下即使有冗余也使得成功送达流量下降 40%。

并且，针对其他解决方案的不足：如中心化调度导致的数据中心场景下流量快速变化的反应不足，局部路由特性对全局掌握不佳，基于终端主机的传输层协议增加传输层复杂度并且无法控制绕开内核具有自身协议栈的高性能应用，提出了属于自己的方案：

• 分布式框架，允许在 RTT 尺度下进行拥塞反应。
• 全局拥塞信息控制，leaf-leaf 控制快速传输网络拥塞指标
• 独立于传输层的网络层部署，避免影响终端主机和引入复杂的传输层控制。

需要满足：高效性，传输层独立，不对称性稳定，可增量部署，可以针对 Leaf-spine 拓扑优化。

class Solution {
public:
    int candy(vector<int>& ratings) {
        // Two times iteration.
        vector<int> ans;
        int count = 1;
        ans.emplace_back(count++);
        for(int i = 1; i < ratings.size(); i++) {
            if(ratings[i] > ratings[i-1]) {
                ans.emplace_back(count++);
            }
            else {
                count = 1;
                ans.emplace_back(count++);
            }
        }
        

        #ifdef DEBUG
        cout << ans.size() << ' ' << ratings.size() << '\n';
        for(int i = 0; i < ans.size(); i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
        #endif

        count = 1;
        for(int i = ratings.size() - 1; i > 0; i--) {
            if(ratings[i-1] > ratings[i]) {
                ans[i-1] = max(ans[i-1], ++count);
            }
            else {
                count = 1;
                ans[i-1] = max(ans[i-1], count);
            }
        }
        
        #ifdef DEBUG
        cout << ans.size() << ' ' << ratings.size() << '\n';
        for(int i = 0; i < ans.size(); i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
        #endif

        return reduce(ans.begin(), ans.end());
    }
};

func candy(ratings []int) int {
	n := int(len(ratings))
	ans := make([]int, n)
	count := 1
	ans[0] = count
	count++

	for i := 1; i < n; i++ {
		if ratings[i-1] < ratings[i] {
			ans[i] = count
			count++
		} else {
			count = 1
			ans[i] = count
			count++
		}
	}

	count = 1
	for i := n - 1; i > 0; i-- {
		if ratings[i-1] > ratings[i] {
			count++
			ans[i-1] = max(ans[i-1], count)
		} else {
			count = 1
		}
	}
	var final int = 0
	for i := 0; i < n; i++ {
		final = final + ans[i]
	}
	return final
}

好麻烦的题目

class Solution {
    public:
        bool isPrintable(vector<vector<int>>& targetGrid) {
            // The tuple has color -> (up, down, left, right).
            unordered_map<int, tuple<int,int,int,int>> color_mat;

            // Find the tuple mat from the graph.
            for(int i = 0; i < targetGrid.size(); i++) {
                for(int j = 0; j < targetGrid[i].size(); j++) {
                    int color = targetGrid[i][j];
                    if(color_mat.find(color) == color_mat.end()) {
                        color_mat[color] = make_tuple(INT_MAX / 2, 0, INT_MAX / 2, 0);
                    }
                    const auto & [up, down, left, right] = color_mat[color];
                    color_mat[color] = make_tuple(min(up, i), max(down, i), min(left, j), max(right, j));
                }
            }

            // Search the matrix and find the topology order.
            unordered_map<int, unordered_set<int>> graph;
            unordered_map<int, int> inDegree;
            for(const auto & ele: color_mat) {
                const int & color = ele.first;
                const auto & [up, down, left, right] = ele.second;
                graph[color] = unordered_set<int>();
                if(inDegree.find(color) == inDegree.end()) {
                    inDegree[color] = 0;
                }
                for(int i = up; i <= down; i++) {
                    for(int j = left; j <= right; j++) {
                        if(targetGrid[i][j] != color && graph[color].find(targetGrid[i][j]) == graph[color].end()) {
                            graph[color].insert(targetGrid[i][j]);
                            inDegree[targetGrid[i][j]]++;
                        }
                    }
                }
            }
            
            int n = graph.size();
            queue<int> q;
            int count = 0;
            for(const auto & ele: inDegree) {
                if(ele.second == 0) {
                    q.emplace(ele.first);
                }
            }

            while(!q.empty()) {
                int cur = q.front();
                q.pop();
                count++;
                for(const auto & adj: graph[cur]) {
                    if(--inDegree[adj] == 0) {
                        q.emplace(adj);
                    }
                }
            }

            #ifdef DEBUG
            for(const auto & element: color_mat) {
                const auto & [u,d,l,r] = color_mat[element.first];
                cout << element.first << ":(" << u << ',' << d << ',' << l << ',' << r << ")\n";
            }

            for(const auto & element: graph) {
                cout << element.first << " -> (";
                for(const auto & adj: element.second) {
                    cout << adj << ',';
                }
                cout << '\n';
            }

            for(const auto & element: inDegree) {
                cout << element.first << ": " << element.second << '\n';
            }

            cout << count << ' ' << n << '\n';
            #endif

            return count == n;
        }
    };

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        // 2 times bfs. First get all the boxes final status. Second get the candies.
        queue<int> q;
        for(const auto & init: initialBoxes) {
            q.emplace(init);
        }
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            if(status[cur] == 1) {
                for(const auto & key: keys[cur]) {
                    status[key] = 1;
                }
            }
            for(const auto & adj: containedBoxes[cur]) {
                q.emplace(adj);
            }
        }
        // Then get the boxes candies.
        int ans = 0;
        for(const auto & init: initialBoxes) {
            q.emplace(init);
        }
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            if(status[cur] == 1) {
                ans += candies[cur];
            }
            for(const auto & adj: containedBoxes[cur]) {
                q.emplace(adj);
            }
        }
        return ans;
    }
};

事务基础与并发控制

事务

• 事务 (Transaction) 是什么？
  • 是一组数据库运算的集合，可以抽象成一个的不可分的逻辑工作单元

ACID 特性

• 事务具有 ACID 特性
  • Atomicity: 原子性，即不可分割。事务要么完全执行，要么完全不执行。
  • Consistency: 事务必须保持数据库系统满足持续性，也就是满足数据库系统中的原先拥有的关系和条件。
  • Isolation: 隔离性，每个事务都是独立运行，相当于仅仅在单独运行自己。
  • Durability: 持续性。事务必须可以从错误中恢复。

并发控制

• 什么是并发控制？并发控制的目的是什么？
  • 并发控制是数据库系统保证多个事务运算正确交叠的机制。目的是为了保证事务之间的隔离性，同时增加数据库处理速度，提高吞吐率。

保证正确的交叠：从序列化执行开始

为了简化调度方式，将数据库内的所有操作都看做仅有对特定资源的读取和写入操作。我们用 $R_i(A)$ 表示第 i 个事务读取数据 A，$W_i(A)$ 表示第 i 个事务写入数据 A。

序列化调度与等价调度

• 没有任何交叠操作的调度 -> 序列化调度。即完成一个事务的所有操作才去执行下一个事务的操作。
• 等价调度是一组执行效果相同的调度的集合。

可以序列化的调度

• 具有交叠操作的调度等价于某些事务的序列化操作。
• 每个可序列化的调度都可以确保持续性的时候，我们的序列化调度是可持续的。
• 需要我们判断调度是否可序列化。

判断调度可序列化

矛盾操作

• 一对矛盾的操作将具有：
  • 不同的事务面向同一份资源。
  • 至少有一个操作是写操作。
• 这样我们有：(R1W2 不可重复读),(W1R2 脏页读),(W1W2 更新丢失) 均为矛盾操作。（目前不考虑假性读取和写入偏移）

可序列化的不同层级

• 冲突可序列 (confilict serializability)

  • 两个调度是冲突等价的，当且仅当
    • 拥有相同事务且事物内部操作相同。
    • 两个调度中冲突操作的顺序是相同的。也就是说如果调度一中是 (R1W2),那么调度二也必须保证 R1 在 W2 之前。
  • 调度 $S$ 是冲突可序列的，当它
    • 在冲突操作上的顺序与某些序列化调度相同。也就是说，你可以将他转换成序列化调度。

• 视图可序列 (view serializability)

  • 两个调度是视图等价的当它们
    • 事务 1 在调度 1 中读取的初始值和在调度 2 中读取的初始值相同。
    • 事务 1 在调度 1 中读取到事务 i 写入的值，则在调度 2 中也应该读取到事务 i 写入的值。
    • 所有的最终结果都必须由一个事务来完成。

• 很显然冲突可序列化是比视图可序列化更严格 的。

前序图

• 判断是否冲突可序列化的简单的方法。
• 每个事务作为一个节点。每个冲突操作对作为一条边。
• 当前序图是有向无环图时，恭喜你它是冲突可序列化的。

并发控制方法

为了保证得到正确的交叠操作调度，我们需要一些并发控制方法。

锁的类型（其实是读写锁换皮）

• 共享锁：用于读操作的共享锁。
• 排它锁：用于写操作的排它锁。

简单的排它锁和共享锁无法保证可序列性。

二阶段锁

• 阶段一：获得锁

  • 每个事务获取他所需要的锁。
  • 可能被拒绝或允许，但是在该阶段不允许有释放锁的行为。

• 阶段二：释放锁

  • 每个事务释放它所需要的锁。
  • 不允许任何事务获得锁。
  • 严格的二阶段锁：在所有事务结束后才能统一释放锁。可以解决脏页读问题。
  • 二阶段锁可能导致死锁。通过检测和预防来避免死锁 (银行家算法等...)
  • 这里不探索如何解决死锁。

• 一个调度是严格的当一个事务写入一份数据后，其他事务不能读取或覆盖这份数据，直到该事务终结。

• 可以看出严格程度：严格序列化 > 严格二阶段锁 > 冲突可序列化 > 视图可序列化

时间戳排序控制 (T/O)

• 采用时间戳来决定序列化调度中事务执行的顺序。当 TS(T1)<TS(T2) 的时候，执行顺序必须为 T1 -> T2.
• 基础时间戳
  • 事务自身将拥有时间戳；TS( $T_i$ )
  • 每个数据对象也将有自己的时间戳。
    • 数据 X 的读时间戳：R(X)
    • 数据 X 的写时间戳：W(X)

基础时间戳控制

• 读操作

  • 当 TS(T) < W(X) 的时候，回滚并重新开始，赋予新的 TS(T).
  • 否则持续执行并且 $R(X)=\max(R(X),TS(T))$.
  • 允许拷贝一份 X 来保证重复读取。

• 写操作

  • 当 TS(T) < W(X) 或者 TS(T) < R(X) 的时候，回滚并重新开始，赋予新的 TS(T).
  • 否则持续执行并且 $W(X)=\max(W(X),TS(T))$

• 基础的时间戳操作保证了冲突可序列性质。

托马斯写 + 时间戳控制

• 写操作处有所不同。

  • 当 TS(T) < R(X) 的时候，回滚。
  • 当 TS(T) < W(X) 的时候，忽略写操作，继续执行（因为很快时间戳后面的事务的写操作将覆盖本次的写操作）。
  • 否则持续执行并且 $W(X)=\max(W(X),TS(T))$

• 很明显仅保证视图可序列性。

OCC(乐观并发控制)

• 时间戳协议。
• DBMS 为每一个事务创建了一个私有的工作空间。
  • 每个被读取的对象将被复制到工作空间中，对对象的编辑也将加入到工作空间中。
  • 当事务提交时，DBMS 将会对比工作空间写集合，每个事务的写空间相同时，装载到全局数据库中。

三阶段

• Read，读取。跟踪每个事务的读、写集合，储存他们的写入对象到私有的工作空间中。DBMS 将会复制一个事务中所有需要的元组到共享数据库中保证可重复读。
• Validation，验证。给每一个事务独有的时间戳，检查他们是否于其他对象相互冲突。
  • 当事务唤起提交时，进入验证部分。
  • 前向验证：检查正在提交中的事务读/写集合是否与活动中的未提交事务相互重叠。
    • 检查时间戳。当提交事务时间戳小于其他活动事务时，需要满足三个条件：
      • (1) 其他事务读阶段位于当前事务写阶段完成之后。R2(A)>W1(A)
      • (2) 其他事务写阶段在当前事务写阶段完成之后。W2(A)>W1(A)， 并且 当前事务没有修改任何其他活动事务要读取的对象。
      • (3) 其他事务读阶段在当前事务读阶段完成之后。R2(A)>R1(A), 并且当前事务不修改任何T2 将会读取或写入的对象。
    • 反向验证：检查正在提交中的事务读/写集合是否与活动中的已提交事务相互重叠。仍然遵循三条原则。
• Write，写。当验证成功时，对所有已经编辑过的对象设置写时间戳，装载他们进入全局数据空间。否则回滚，中断事务。

class Solution {
public:
    string lastSubstring(string s) {
        int i = 0, j = 1, n = s.size();
        while (j < n) {
            int k = 0;
            while (j + k < n && s[i + k] == s[j + k]) {
                k++;
            }
            if (j + k < n && s[i + k] < s[j + k]) {
                int t = i;
                i = j;
                j = max(j + 1, t + k + 1);
            } else {
                j = j + k + 1;
            }
        }
        return s.substr(i, n - i);
    }
    string answerString(string word, int numFriends) {
        if(numFriends == 1) {
            return word;
        }
        string last = lastSubstring(word);
        int n = word.size(), m = last.size();
        return last.substr(0, min(m, n - numFriends + 1));
    }
};

#define DEBUG
#undef DEBUG
class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> graph;
        unordered_map<char, int> inDegree;
        bool flag = false;
        auto add_edge = [&](const string & l, const string & r) -> void {
            int i = 0;
            for(i = 0; i < min(l.length(), r.length()); i++) {
                if(graph.find(l[i]) == graph.end()) {
                    graph[l[i]] = unordered_set<char>();
                }
                if(inDegree.find(l[i]) == inDegree.end()) {
                    inDegree[l[i]] = 0;
                }
                if(l[i] != r[i] && graph[l[i]].find(r[i]) == graph[l[i]].end()) {
                    flag = true;
                    graph[l[i]].insert(r[i]);
                    inDegree[r[i]]++;
                    break;
                }
                else if(l[i] != r[i]) {
                    flag = true;
                    break;
                }
            }
            if(!flag && l.length() > r.length()) {
                return;
            }
            flag = true;
            int temp = i;
            for(; i < l.length(); i++) {
                if(graph.find(l[i]) == graph.end()) {
                    graph[l[i]] = unordered_set<char>();
                }
                if(inDegree.find(l[i]) == inDegree.end()) {
                    inDegree[l[i]] = 0;
                }
            }
            i = temp;
            for(; i < r.length(); i++) {
                if(graph.find(r[i]) == graph.end()) {
                    graph[r[i]] = unordered_set<char>();
                }
                if(inDegree.find(r[i]) == inDegree.end()) {
                    inDegree[r[i]] = 0;
                }
            }
        };

        // Step 1: Add edges.
        if(words.size() == 1) {
            flag = true;
            for(int i = 0; i < words[0].length(); i++) {
                if(graph.find(words[0][i]) == graph.end()) {
                    graph[words[0][i]] = unordered_set<char>();
                }
                if(inDegree.find(words[0][i]) == inDegree.end()) {
                    inDegree[words[0][i]] = 0;
                }
            }
        }
        else {
            for(int i = 0; i < words.size(); i++) {
                for(int j = i + 1; j < words.size(); j++) {
                    add_edge(words[i], words[j]);
                }
            }
        }

        #ifdef DEBUG
        for(auto & elem: graph) {
            cout << elem.first << ": ";
            for(const auto & adj: elem.second) {
                cout << adj << ' ';
            }
            cout << '\n';
        }
        for(auto & elem: inDegree) {
            cout << elem.first << ": " << elem.second << "\n";
        }
        string flag_str = (flag == true) ? "true" : "false";
        cout << flag_str << '\n';
        #endif

        // Step 2: TopoSort.
        queue<char> q;
        string ans;
        for(const auto & ch: inDegree) {
            if(ch.second == 0) {
                q.emplace(ch.first);
            }
        }
        while(!q.empty()) {
            char ch = q.front();
            ans.push_back(ch);
            q.pop();
            for(const auto & adj: graph[ch]) {
                if(--inDegree[adj] == 0) {
                    q.emplace(adj);
                }
            }
        }
        return ans.length() == graph.size() && flag ? ans : "";
    }
};

基于基环树的思想。

class Solution {
public:
    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        vector<vector<int>> reverse_graph(n);
        queue<int> q;
        vector<int> inDegree(n, 0);

        for(int i = 0; i < n; i++) {
            inDegree[favorite[i]]++;
        }
        for(int i = 0; i < n; i++) {
            if(inDegree[i] == 0) {
                q.emplace(i);
            }
        }

        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            // Build reverse_graph;
            reverse_graph[favorite[cur]].emplace_back(cur);
            if(--inDegree[favorite[cur]] == 0) {
                q.emplace(favorite[cur]);
            }
        }
        
        // Dfs reverse graph find the shortest edge.
        auto dfs = [&](this auto && dfs, int from) -> int {
            int max_depth = 1;
            for(const auto & adj: reverse_graph[from]) {
                max_depth = max(max_depth, dfs(adj) + 1);
            }
            return max_depth;
        };

        // Find the cycle.
        int ring = 0, chain = 0;
        for(int i = 0; i < n; i++) {
            if(inDegree[i] == 0) {
                continue;
            }
            inDegree[i] = 0;
            int tmp_ring = 1;
            for(int adj = favorite[i]; adj != i; adj = favorite[adj]) {
                inDegree[adj] = 0;     // mark as visited.
                tmp_ring++;
            }
            
            if(tmp_ring == 2) {
                chain = chain + dfs(i) + dfs(favorite[i]);
            } else {
                ring = max(ring, tmp_ring);
            }
        }
        return max(chain, ring);
    }
};

// #define debug
class Union {
        public:
        vector<int> parent;
        int n;
        // The Costruction function.
        Union(int n):n(n),parent(vector<int>(n)) {
            iota(parent.begin(), parent.end(), 0);
        }
    
        // Path compression. Find parent until the same.
        int find(int id) {
            if(parent[id] != id) {
                parent[id] = find(parent[id]);
            }
            return parent[id];
        }
    
        // Merge by size. You can also make it by rank, for modified as size[pa_i] += 1;
        void merge(int id1, char id2) {
            // Find parent.
            int pa1 = find(id1);
            int pa2 = find(id2);
    
            if(pa1 == pa2) {
                return;
            }
            else if(pa1 < pa2) {
                parent[pa2] = pa1;
            }
            else {
                parent[pa1] = pa2;
            }
        }
    
        bool judge(int id1, int id2) {
            return find(id1) != find(id2);
        }
    };
class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        Union u(26);
        for(int i = 0; i < s1.length(); i++) {
            u.merge(s1[i] - 'a', s2[i] - 'a');
        }
        #ifdef debug
        for(auto & element: u.parent) {
            cout << element.first << ' ' << element.second << '\n';
        }
        #endif
        string ans;
        for(int i = 0; i < baseStr.length(); i++) {
            ans.push_back(u.find(baseStr[i] - 'a') + 'a');
        }
        return ans;
    }
};

class Solution {
public:
    string robotWithString(string s) {
        int n = s.length();
        vector<char> min_str(n+1);
        min_str[n] = 'z';
        for(int i = n - 1; i >= 0; i--) {
            min_str[i] = min(min_str[i+1], s[i]);
        }
        stack<char> st;
        string ans;
        for(int i = 0; i < n; i++) {
            st.push(s[i]);
            while(!st.empty() && st.top() <= min_str[i+1]) {
                ans.push_back(st.top());
                st.pop();
            }
        }
        return ans;
    }
};

template<typename T>
class DataStructure {
        public:
        // Data Definition start
        // ********
        // Data Definition end
        std::shared_mutex rwlock;
        
        template<typename T>
        T read() {
                std::shared_lock rlock(rwlock);  // Read operations with shared_lock;
                // Read Operations;
        }
        template<typename T>
        void write() {
                std::unique_lock wlock(rwlock);  // Write operations with exclusive_lock.
                // Write operations;
        }
};

#include<ranges>
class Solution {
    public:
        string clearStars(string s) {
            vector<stack<int>> indices(26, stack<int>());
            int count = 0;
            for(int i = 0; i < s.length(); i++) {
                if(s[i] == '*') {
                    for(int i = 0; i < 26; i++) {
                        if(!indices[i].empty()) {
                            s[indices[i].top()] = '*';
                            indices[i].pop();
                            break;
                        }
                    }
                } else indices[s[i] - 'a'].push(i);
            }
            return s | ranges::views::filter([](char i) {return i != '*';}) 
                    | ranges::to<std::string>();
        }
    };

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        // TopoSort to modify the graph.
        int n = edges.size();
        vector<int> inDegree(n, 0);
        for(int i = 0; i < n; i++) {
            if(edges[i] != -1) inDegree[edges[i]]++;
        }
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(inDegree[i] == 0) {
                q.emplace(i);
            }
        }
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            int adj = edges[cur];
            edges[cur] = -1;
            if(adj != -1 && --inDegree[adj] == 0) {
                q.emplace(adj);
            }
        }
        int ans = -1;
        auto dfs = [&](this auto && dfs, int from) -> int {
            int nxt = edges[from];
            if(nxt == -1) return 0;
            edges[from] = -1;
            return dfs(nxt) + 1;
        };
        for(int i = 0; i < n; i++) {
            ans = max(ans, dfs(i));
        }
        return ans == 0 ? -1 : ans;
    }
};

class Solution {
public:
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        // Build graph.
        vector<vector<int>> graph(n);
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1];
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
        }
        int * distance = new int [n];
        // Dijkstra with delete the edge. For indirect graph, pick one side, run dijkstra.
        // Directed should strictly follow start and end point.
        auto bfs = [&](int u, int v) -> void {
            queue<int> q;
            q.emplace(u);
            distance[u] = 0;
            while(!q.empty()) {
                int cur = q.front();
                q.pop();
                for(const auto & adj: graph[cur]) {
                    // False delete.
                    if(cur == u && adj == v) {
                        continue;
                    }
                    // Updated.
                    else if(distance[adj] < 0x7f7f7f7f) {
                        continue;
                    }
                    else if(distance[adj] > distance[cur] + 1) {
                        distance[adj] = distance[cur] + 1;
                        q.emplace(adj);
                    }
                }
            }
        };
        int ans = INT_MAX / 2;
        for(const auto & edge: edges) {
            memset(distance, 0x7f, sizeof(int) * n);
            int u = edge[0], v = edge[1];
            bfs(u, v);
            ans = min(ans, distance[v] + 1);
        }
        return ans == INT_MAX / 2 ? -1 : ans;
    }
};

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        auto dfs = [&](this auto && dfs, int start) -> void {
            if(start > n) {
                return;
            }
            ans.emplace_back(start);
            dfs(start * 10);
            for(int i = 1; i <= 9; i++) {
                if(start + i <= n && (start + i) % 10 != 0) {
                    ans.emplace_back(start + i);
                } else {
                    break;
                }
                dfs(10 * (start + i));
            }
        };
        dfs(1);
        return ans;
    }
};

class Solution {
public:
    int getSteps(int curr, long n) {
        int steps = 0;
        long first = curr, last = curr;
        while(first <= n) {
            steps += min(last,n) - first + 1;
            first *= 10;
            last = last * 10 + 9;
        }
        return steps;
    }
    int findKthNumber(int n, int k) {
        int curr = 1;
        k--;
        while(k > 0) {
            int steps = getSteps(curr, n);
            if(steps <= k) {
                k -= steps;
                curr++;
            } else {
                curr = curr * 10;
                k--;
            }
        }
        return curr;
    }
};

class Union {
        public:
        vector<int> parent;
        vector<int> size;
        int components;
    
        // The Costruction function.
        Union(int n): 
            parent(vector<int>(n)), 
            size(vector<int>(n,1)),
            components(n) 
        {
            iota(parent.begin(), parent.end(), 0);
        }
    
        // Path compression. Find parent until the same.
        int find(int id) {
            if(parent[id] != id) {
                parent[id] = find(parent[id]);
            }
            return parent[id];
        }
    
        // Merge by size. You can also make it by rank, for modified as size[pa_i] += 1;
        void merge(int id1, int id2) {
            // Find parent.
            int pa1 = find(id1);
            int pa2 = find(id2);
    
            if(pa1 == pa2) {
                return;
            }
    
            if(size[pa1] < size[pa2]) {
                parent[pa1] = pa2;
                size[pa2] += size[pa1];
            }
            else {
                parent[pa2] = pa1;
                size[pa1] += size[pa2];
            }
            if(pa1 != pa2)
                components--;
        }
    
        bool judge(int id1, int id2) {
            return find(id1) != find(id2);
        }
    };

inline int find(vector<int> & parent,int id) {
    if(id != parent[id]) {
        return find(parent,parent[id]);
    }
    return parent[id];
}
inline void merge(vector<int> & parent,vector<int> & size, int id1, int id2) {
    int pa1 = find(parent,id1);
    int pa2 = find(parent,id2);
    if(pa1 == pa2) {
        return;
    }
    // small merge to big.
    if(size[pa1] < size[pa2]) {
        parent[pa1] = pa2;
        size[pa1] += size[pa2];
    } else {
        parent[pa2] = pa1;
        size[pa2] += size[pa1];
    }
}
inline bool judge(vector<int> & parent,int id1, int id2) {
    return find(parent,id1) == find(parent,id2);
}
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> parent(static_cast<int>(edges.size() + 1));
        iota(parent.begin(), parent.end(), 0);
        vector<int> size(static_cast<int>(edges.size() + 1), 1);
        vector<int> ans;
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1];
            if(!judge(parent, u, v)) {
                merge(parent, size, u,v);
            }
            else {
                ans={u,v};
                break;
            }
        }
        return ans;
    }
};

class Union {
    public:
    int * ancestors;
    int * size;
    int n;

    public:
    Union(int n):n(n) {
        ancestors = new int [n];
        size = new int [n];
        for(int i = 0; i < n; i++) {
            ancestors[i] = i;
            size[i] = 1;
        }
    }
    int find(int id) {
        if(id != ancestors[id]) {
            ancestors[id] = find(ancestors[id]);
        }
        return ancestors[id];
    }
    void merge(int id1, int id2) {
        int pa1 = find(id1);
        int pa2 = find(id2);

        if(pa1 == pa2) {
            return;
        } else if(size[pa1] > size[pa2]) {
            size[pa1] += size[pa2];
            ancestors[pa2] = pa1;
        } else {
            size[pa2] += size[pa1];
            ancestors[pa1] = pa2;
        }
    }
    bool judge(int id1, int id2) {
        return find(id1) == find(id2);
    }
};
class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        Union un(n+1);
        int conflict = -1;       // Mark conflict apperance.
        int loop = -1;
        int * parents = new int [n+1];
        for(int i = 0; i < n + 1; i++) {
            parents[i] = i;
        }
        // Two parent: Conflict.
        // Same ancestor
        for(int i = 0; i < n; i++) {
            int u = edges[i][0], v = edges[i][1];
            if(parents[v] != v) {
                conflict = i;
            } else {
                parents[v] = u;
                int pa_u = un.find(u);
                int pa_v = un.find(v);
                if(pa_u == pa_v) {
                    loop = i;
                } else {
                    un.merge(u, v);
                }
            }
        }

        if(conflict == -1) {
            return edges[loop];
        } else {
            int u = edges[conflict][0], v = edges[conflict][1];
            if(loop == -1) {
                return edges[conflict];
            } else {
                return vector<int>{parents[v], v};
            }
        }
    }
};

class Solution {
    public:
        vector<int> countVisitedNodes(vector<int>& edges) {
            int n = edges.size();
            queue<int> q;
            int * inDegree = new int [n];
            int * mark = new int [n];  // Mark vertex as loop node = 0 or as chain node. chain = 1.
            vector<int> ans(n, 1);
            memset(inDegree, 0, sizeof(int) * n);
            memset(mark, 0, sizeof(int) * n);
            // O(n)
            for(int i = 0; i < n; i++) {
                inDegree[edges[i]]++;
            }
            // O(n)
            for(int i = 0; i < n; i++) {
                if(inDegree[i] == 0) {
                    q.emplace(i);
                }
            }
            while(!q.empty()) {
                int cur = q.front();
                mark[cur] = 1;
                q.pop();
                if(--inDegree[edges[cur]] == 0) {
                    q.emplace(edges[cur]);
                }
            }
            int loop = 1;
            auto dfs = [&](this auto && dfs, int from) -> void {
                int next = edges[from];
                if(mark[next] == 2 || next == -1) {
                    mark[from] = 2;
                    ans[from] = loop;
                    return;
                }
                edges[from] = -1;
                mark[from] = 2;     // visited.
                loop++;
                dfs(next);
                ans[from] = loop;
            };
            for(int i = 0; i < n; i++) {
                if(mark[i] == 1 || mark[i] == 2) continue;
                loop = 1;
                dfs(i);
            }
            int start, chain;
            auto dfs2 = [&](this auto && dfs, int start) -> void {
                int next = edges[start];
                if(mark[next] == 2 || edges[next] == -1) {
                    chain += ans[next];
                    ans[start] = chain;
                    mark[start] = 2;
                    return;
                }
                mark[start] = 2;
                dfs(next);
                ans[start] = ++chain;
            };
            for(int i = 0; i < n; i++) {
                if(mark[i] == 2) continue;
                start = i;
                chain = 1;
                dfs2(start);
            }
            return ans;
        }
    };

typedef struct Node {
    int v;
    int w;
    struct Node * next;
} Node;

void node_init(Node * obj, int to, int weight) {
    obj -> v = to;
    obj -> w = weight;
    obj -> next = NULL;
}

typedef struct DiGraph {
    int n;
    Node ** headers;
    Node ** tails;
} DiGraph;

void BuildGraph(DiGraph * obj, int n, int ** times, int timesSize) {
    obj -> n = n;
    obj -> headers = (Node **) malloc(sizeof(Node *) * n);
    obj -> tails = (Node **) malloc(sizeof(Node *) * n);
    for(int i = 0; i < n; i++) {
        obj -> headers[i] = (Node *) malloc(sizeof(Node));
        node_init(obj -> headers[i], i, 0);
        obj -> tails[i] = obj -> headers[i];
    }
    for(int i = 0; i < timesSize; i++) {
        int u = times[i][0] - 1, v = times[i][1] - 1, w = times[i][2];
        obj -> tails[u] -> next = (Node *)malloc(sizeof(Node));
        obj -> tails[u] = obj -> tails[u] -> next;
        node_init(obj -> tails[u], v, w);
    }
}

typedef struct min_heap {
    int n;
    int size;
    Node * node;
} min_heap;

void init_min_heap(min_heap * obj, int n) {
    obj -> n = n;
    obj -> size = 0;
    obj -> node = (Node *) malloc(sizeof(Node) * n);
}

int parent(int i) {
    return (i + 1) / 2 - 1 > 0 ? (i + 1) / 2 - 1 : 0;
}
int left_child(int i) {
    return i * 2 + 1;
}
int right_child(int i) {
    return (i + 1) * 2;
}

void min_heapify(min_heap * obj, int i) {
    if(i >= obj -> size) {
        return;
    }

    int lchild = left_child(i);
    int rchild = right_child(i);
    
    // swap the smallest up.
    int smallest = i;
    if(lchild < obj -> size && obj -> node[lchild].w < obj -> node[smallest].w) {
        smallest = lchild;
    }
    else smallest = i;
    if(rchild < obj -> size && obj -> node[rchild].w < obj -> node[smallest].w) {
        smallest = rchild;
    }
    if(smallest != i) {
        Node temp = obj -> node[i];
        obj -> node[i] = obj -> node[smallest];
        obj -> node[smallest] = temp;
        min_heapify(obj, smallest);
    }
}

Node top(min_heap * obj) {
    return obj -> node[0];
}

void pop(min_heap * obj) {
    if(obj -> size == 0) {
        return;
    }

    Node minimum = obj -> node[0];
    obj -> node[0] = obj -> node[obj -> size - 1];
    obj -> size--;
    min_heapify(obj, 0);
}

void push(min_heap * obj, Node node) {
    obj -> size++;
    obj -> node[obj -> size - 1] = node;
    for(int i = obj -> size - 1; i >= 0; i = parent(i)) {
        if(obj -> node[parent(i)].w > obj -> node[i].w) {
            Node tmp = obj -> node[parent(i)];
            obj -> node[parent(i)] = obj -> node[i];
            obj -> node[i] = tmp;
        }
        else break;
    }
}

char empty(min_heap * obj) {
    return obj -> size == 0;
}

int networkDelayTime(int** times, int timesSize, int* timesColSize, int n, int k) {
    DiGraph * digraph = (DiGraph *) malloc(sizeof(DiGraph));
    BuildGraph(digraph, n, times, timesSize);

    min_heap * test_heap = (min_heap *) malloc(sizeof(min_heap));
    init_min_heap(test_heap, timesSize);
    int * visited = (int *) malloc(sizeof(int) * n);
    int * distance = (int *) malloc(sizeof(int) * n);
    memset(visited, 0, sizeof(int) * n);
    memset(distance, 0x7f, sizeof(int) * n);
    visited[k - 1] = 1;
    distance[k - 1] = 0;
    Node cur;
    node_init(&cur, k - 1, 0);
    push(test_heap, cur);
    while(!empty(test_heap)) {
        cur = top(test_heap);
        pop(test_heap);
        int cur_v = cur.v, cur_w = cur.w;
        for (Node * adj = digraph -> headers[cur_v]; adj != NULL; adj = adj -> next) {
            int adj_v = adj -> v, adj_w = adj -> w;
            if(distance[adj_v] > distance[cur_v] + adj_w) {
                distance[adj_v] = distance[cur_v] + adj_w;
                Node tmp;
                node_init(&tmp, adj_v, distance[adj_v]);
                push(test_heap, tmp);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans = ans < distance[i] ? distance[i] : ans;
    }
    return (ans == 0x7f7f7f7f) ? -1 : ans;
}

#include<ranges>
class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        vector<vector<pair<int,int>>> graph(n);
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].emplace_back(v,w);
            graph[v].emplace_back(u,w);
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.emplace(0,0);
        vector<int> distance(n, INT_MAX);
        vector<int> visited(n, 0);
        distance[0] = 0;

        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(visited[cur]) continue;
            visited[cur] = 1;
            for(const auto & [adj, w]: graph[cur]) {
                if(disappear[adj] > w + distance[cur] && distance[adj] > w + distance[cur]) {
                    distance[adj] = distance[cur] + w;
                    pq.emplace(distance[adj], adj);
                }
            }
        }
        return distance | ranges::views::transform([](int i){
            return (i == INT_MAX) ? -1 : i;
        }) | ranges::to<vector<int>>();
    }
};

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<double, int>>> graph(n);
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1];
            double w = succProb[i];
            graph[u].emplace_back(w, v);
            graph[v].emplace_back(w, u);
        }
        priority_queue<pair<double, int>> pq;
        vector<double> distance(n, 0);
        vector<int> visited(n, 0);
        pq.emplace(1, start);
        distance[start] = 1;
        while (!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if (visited[cur]) {
                continue;
            }
            visited[cur] = 1;
            for (auto& [w, adj] : graph[cur]) {
                if (distance[adj] < distance[cur] * w) {
                    distance[adj] = distance[cur] * w;
                    pq.emplace(distance[adj], adj);
                }
            }
        }
        return distance[end];
    }
};

constexpr int MOD = 1e9 + 7;
class Solution {
    vector<vector<pair<int,int>>> graph;
    vector<int> distance, visited, dp;
    int num;
public:
    int dfs(int cur) {
        if(cur == num) {
            return 1;
        } else if(dp[cur] != -1) {
            return dp[cur];
        }
        int ans = 0;
        for(const auto & adj: graph[cur]) {
            int nxt = adj.first;
            if(distance[cur] > distance[nxt]) {
                ans = (ans + dfs(nxt)) % MOD;
            }
        }
        dp[cur] = ans;
        return ans;
    }
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        num = n;
        graph = vector<vector<pair<int,int>>>(n + 1);
        // 1 as start index.
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].emplace_back(v,w);
            graph[v].emplace_back(u,w);
        }
        priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.emplace(0, n);
        distance = vector<int>(n+1, INT_MAX);
        visited = vector<int>(n+1, 0);
        distance[n] = 0;
        // Dijkstra started from last node.
        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(visited[cur] == 1) continue;
            visited[cur] = 1;
            for(const auto & [adj, w]: graph[cur]) {
                if(distance[adj] > distance[cur] + w) {
                    distance[adj] = distance[cur] + w;
                    pq.emplace(distance[adj], adj);
                }
            }
        }
        // Distance to LastNode complete.
        dp = vector<int>(n+1, -1);
        dp[n] = 1;
        return dfs(1);
    }
};

class Solution {
public:
    int maxDifference(string s, int k) {
        const int inf = INT_MAX / 2;
        int ans = -inf;
        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 5; y++) {
                if (y == x) {
                    continue;
                }
                int cur_s[5]{}, pre_s[5]{};
                int min_s[2][2] = {{inf, inf}, {inf, inf}};
                int left = 0;
                for (int i = 0; i < s.size(); i++) {
                    cur_s[s[i] - '0']++;
                    int r = i + 1;
                    while (r - left >= k && cur_s[x] > pre_s[x] && cur_s[y] > pre_s[y]) {
                        int& p = min_s[pre_s[x] & 1][pre_s[y] & 1];
                        p = min(p, pre_s[x] - pre_s[y]);
                        pre_s[s[left] - '0']++;
                        left++;
                    }
                    ans = max(ans, cur_s[x] - cur_s[y] - min_s[cur_s[x] & 1 ^ 1][cur_s[y] & 1]);
                }
            }
        }
        return ans;
    }
};

using namespace std;
using pii = pair<int,int>;
using tiii = tuple<int,int,int>;
using Graph = vector<vector<tiii>>;
#define RELEASE
class Solution {
public:
    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        // Build graph here. 
        Graph graph(n);
        int ind = 0;
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].emplace_back(v,w,ind);
            graph[v].emplace_back(u,w,ind);
            ind++;
        }
        // iterate the graph now.
        vector<int> distance(n, INT_MAX / 2);
        vector<int> visited(n, 0);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.emplace(0,0);
        vector<vector<int>> pre(n);     // Record the pre vertex of the graph.
        distance[0] = 0;
        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(visited[cur] == 1) continue;
            visited[cur] = 1;
            // Iterate over the adjacent vertices.
            for(const auto & [adj, w, _]: graph[cur]) {
                if(distance[adj] > dist + w) {
                    distance[adj] = distance[cur] + w;
                    pq.emplace(distance[adj], adj);
                }
            }
        }
        vector<char> visited2(n, 0);
        vector<bool> ans(edges.size(), false);
        auto dfs = [&](this auto && dfs, int from) -> void {
            visited2[from] = 1;
            for(const auto & [adj, w, index]: graph[from]) {
                if(distance[adj] + w != distance[from]) {
                    continue;
                }
                ans[index] = true;
                if(!visited2[adj]) {
                    dfs(adj);
                }
            }
        };
        if(distance[n-1] == INT_MAX / 2) return ans;
        dfs(n-1);
        return ans;
    }
};

using plli = pair<long long,int>;
using Graph = vector<vector<pair<int,int>>>;
using ll = long long;
constexpr int MOD = 1e9+7;
#define RELEASE
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        // Build graph here. 
        Graph graph(n);
        for(const auto & edge: roads) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].emplace_back(v,w);
            graph[v].emplace_back(u,w);
        }
        // iterate the graph now.
        vector<ll> distance(n, LLONG_MAX);
        vector<int> visited(n, 0);
        priority_queue<plli, vector<plli>, greater<plli>> pq;
        pq.emplace(0,0);
        distance[0] = 0;
        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(visited[cur] == 1) continue;
            visited[cur] = 1;
            // Iterate over the adjacent vertices.
            for(const auto & [adj, w]: graph[cur]) {
                if(distance[adj] > (ll)dist + w) {
                    distance[adj] = (ll)distance[cur] + w;
                    pq.emplace(distance[adj], adj);
                }
            }
        }

        #ifdef DEBUG
        for(int i = 0; i < n; i++) {
            const auto & adj = pre[i];
            cout << i << ": ";
            for(int i = 0; i < adj.size(); i++) {
                cout << adj[i] << ' ';
            }
            cout << endl;
        }
        #endif

        if(distance[n-1] == LLONG_MAX) return 0;
        vector<int> counts(n, -1);
        auto dfs = [&](this auto && dfs, int from) -> int {
            if(from == 0) {
                counts[from] = 1;
                return 1;
            } else if(counts[from] > -1) {
                return counts[from];
            }
            counts[from] = 0;
            for(const auto & [adj, w]: graph[from]) {
                if(distance[adj] + w == distance[from])  {
                    counts[from] = (counts[from] + dfs(adj)) % MOD;
                }
            }
            return counts[from];
        };
        return dfs(n-1);
    }
};

Docker & k8s

Docker

• 运行于 OS 上的软件，用于创建，管理，编排容器。可以将开发的应用程序自动部署到容器。

• 与 VM 的区别

• docker 应用层抽象，容器间通过网络命名空间进行隔离。多个容器共享一个 OS 内核。

• VM 对物理硬件层抽象，包含独立操作系统。

• 前者为应用环境提供，后者为操作系统环境提供。

• docker 组件

• 引擎（客户端，服务端），docker 镜像，容器，Registry（镜像仓库）

• 架构：Client（Application）-Server（OS）架构。

Docker 引擎

• Docker 引擎主要有：docker 客户端，docker 守护进程 (daemon)，containerd 和 runc。

• 现在的 docker 引擎架构：

• docker client(CLI) 与 docker daemon（API 与其它特性）进行交互。

• docker daemon 与容器的监督者 (supervisor) 进行交互，有 start|stop|pause...等管理容器。

• containerd 负责启动没有守护进程的容器 (shim)，每个 shim 运行时有 runc 作为内核源语接口，与运行容器进行交互。

• Runc: OCI 容器的运行时规范的参考实现。用于创建容器。OCI：运行时标准、容器镜像标准。

• containerd: 进行容器的生命周期管理——start|stop|pause|rm...。现在也可以用于管理镜像，例如拉取、推送，镜像数据/容器数据的存储。

• 根据镜像启动容器：docker container run --name ctrl -it alpine:latest sh

• 基于 alpine:latest 创建一个名为 ctrl 的容器，并进入 shell 环境。

• cli 向 docker 守护进程接收指令，指示在 containerd 启动新的容器。

• containerd 向 runc 传递 OCI 镜像并指示 runc 创建容器并启动 shell 环境。

• 创建容器

• shim：与 daemon 守护解绑，实现没有 daemon 的容器。当创建新容器后，fork 出来的 runc 进程会退出。随后 containerd-shim 进程将成为容器的父进程。shim 将：

• 保持 stdin 和 stdout 开启。daemon 重启时容器不会因为管道关闭而终止。

• 退出状态反馈给 daemon。

Docker 镜像

• 镜像是一个只读的模板，独立的文件系统，（很像一个停止运行的容器），包括运行容器所需的数据，可以用来创建新的容器。

• 容器从镜像启动后，两者之间就变成了互相依赖的关系。在镜像上启动的容器全部停止之前，镜像是无法删除的。

• 镜像仓库：docker 镜像储存在镜像仓库服务中。一个仓库中可以拥有多个镜像。

• 镜像的命名和标签：采用 : 分离。我们可以通过 docker image pull <repo>:<tag> 来拉取镜像。-a 拉取仓库中所有的镜像。

• 一个镜像可以拥有多个标签。

• filter 可以用来过滤。

• 镜像由几个只读的平行层组成。通过docker inspect可以了解这些层之间的关系。修改或创建新的内容时，将会在这些镜像层之上，创建新的镜像层。通过存储引擎（现在是快照）的方式实现堆栈，对外展示成一个统一的文件系统。

• 可以通过多架构镜像来适配当前运行环境。--platform 指定拉取对应架构镜像，也可以指定运行什么架构的容器。

• docker image rm <ID>删除对应 ID 的镜像。同时，docker image rm $(docker image ls -q) -f删除所有本地系统内的镜像。

Docker 容器

• 镜像的运行时实例。通过 docker container run <image> <app> 运行镜像中的某个应用。-it 将当前终端连接到容器的对应终端上，也就是不在幕后运行镜像。

• 容器 vs 虚拟机

• 相同点：都依赖于宿主机，可以是 notebook，可以是物理服务器，也可以是公有云的一个实例。

• 虚拟机：启动后将全部物理资源通过 hypervisor 全部占有，hypervisor 通过将所有的物理资源划分成虚拟资源打包进入 VM 的软件结构中，这样用户可以使用这些虚拟机。虚拟化的是硬件资源。

• 容器：启动后会唤起所选择的操作系统。OS 占有全部的物理资源，在 OS 之上是 docker 引擎，获取 OS 的资源，例如进程树，文件系统和网络栈。接着将资源分割成相互隔离的结构，成为容器。因此虚拟化的是操作系统。

• 运行容器内的应用（例如运行 bash）后，一旦杀死该应用，容器也会退出、终止。因为这是这个容器的主进程。

• 退出容器但是并没有杀死主进程时，容器仍然在运行。此时不能通过 docker run，而是通过docker exec -it <ID> <app>再次连接到进程。

• docker container stop终止容器，docker container rm删除容器。数据在容器删除之前将不会被丢弃。

应用容器化

• 编写应用代码

• dockerfile 创建，包含应用描述，依赖，以及如何运行应用。

• 对 dockerfile 进行docker image build。

• docker 将应用程序构建到 docker 镜像中。

对应的一些指令

• from: 指定基础镜像作为基础镜像层。

• label: 自定义的标签，是一组 KV 对。

• run: 执行基础镜像层的应用，可能会安装新的应用，也是一个镜像层。

• copy: 选取文件复制到当前镜像中，并且新建一个镜像层来存储。

• EXPOSE: 暴露端口。

• ENTRYPOINT: 指定入口程序。不新增镜像层。

• docker image build -t <image>:<tag>.

• 增加新的 tag 用于推送：需要

• 仓库服务，仓库，镜像标签。

• docker image tag <image>:<tag> <repo>/<image>:<tag>

• docker image push推送到上游。

docker compose

• 单引擎进行多容器应用的部署与管理。

• compose 文件可以使用 yaml 或者 json（前者是后者的子集）来编写。默认为 docker-compose.yml。

• docker-compose up启动应用。

• 文件包括：version 版本，service 服务，networks 创建新的网络，volumes 创建新的卷。

docker swarm

• 集群管理。一个 swarm 由一个或多个 docker 节点构成。这些节点可以是服务器，虚拟机，树莓派或者云实例。要求通过可靠网络连接。

• 节点将会被配置成管理节点 (Manager) 或者工作节点 (worker)。

• 管理节点：负责控制平面，监控集群状态，分发工作任务，管理工作节点。

• 工作节点接受来自管理节点的任务并执行。

k8s(kubernetes)

• 开源的容器集群管理，提供集群的自动部署，扩缩容，维护等功能。分为管理节点和工作节点，类似于 docker swarm。

• 通过 CI/CD(持续集成/持续交付) 自动化流程，保证环境一致性 (CI)，并确保集群可以随时部署 (CD).

组件

• etcd: 集群状态。

• apiserver: 提供资源操作的唯一入口，提供认证，授权，访问控制，API 注册，发现等机制。

• controller manager: 集群状态维护。

• scheduler: 资源调度，根据预定调度策略将 pod 调度到相应的机器上。

• kubelet: 负责维护容器的生命周期，同时也负责卷和网络的管理。

• runtime: 镜像管理，pod 和容器的真正运行。

• kube-proxy: service 提供 cluster 内部的服务发现和负载均衡。

一些概念

• Pod：最小的可部署单元。包含一个或者多个紧密耦合的容器。Pod 的主要作用是提供一个环境，可以让容器共享网络和存储资源。并且提供了容器间通信、生命周期管理等功能。

• Deployment：部署无状态应用程序。可以随时获知当前 Pod 的部署进度。

• service: 定义了 Pod 的逻辑集合和访问该集合的策略，是真实服务的抽象。提供了一个统一的服务访问入口和代理服务发现机制，关联多个相同 label 的 pod。

• volume: 卷宗，一个可以被多个容器共同访问的共享目录，定义在 pod 上，可以被一个或多个 pod 中的容器挂载到某个目录下。

• namespace: Multi-tenant 多租户隔离，将集群内部资源对象分配到不同的 namespace 中，形成逻辑上不同的小项目，小组，用户组，便于共享集群资源的同时还能被分别管理，精细化管理的粒度。

• 1Ingress：通过定义规则来管理从外部访问集群内 Service 的流量。

中国电信：AI infra 实习
没有手撕算法部分。（国企这么好的吗）
O、根据简历自我介绍
一、拷打项目：

1. 操作系统项目的简单介绍？
2. 页表是怎么配置的？（内核启动时配置高页表，随后配置低地址页表，随后启动用户态程序）
3. 介绍一下 linux 如何管理内存。(伙伴系统和 slab 分配器)
   3.1 两者的区别是什么？（slab 分配器将内存块作为对象进行管理，进行小内存的分配，较大内存的分配通过页表进行。管理对象的生命周期和分配，这样不会在使用完内存后真正释放内存，降低时延和开销。伙伴系统是真正进行内存管理的工具，减少外部内存碎片，通过 2^n 进行分配防止内存碎片。）
   3.2 slab 分配器的管理数据结构？（红黑树）。
4. IPC 通信方式你选择了什么？（共享内存，这样每个进程访问相同的物理内存，提高进程通信效率）
   4.1 每个进程是怎样访问相同的物理内存的？（通过自身的虚拟地址空间，以及自身的页表通过 TLB 的方式来进行地址翻译成为物理内存进行访问）。
   小结：操作系统问的不深。没有问到特别高深的技术（写时拷贝，锁，时钟中断 IRQ 等）

二、拷打项目：

1. 介绍以下你的阵列是如何进行加速的？
   （脉动阵列 (systolic array)，专门为矩阵运算进行翻译和加速。矩阵运算取的是两个矩阵的一行、一列进行乘累加操作，因此可以让矩阵的一行自左向右进入乘累加单元，让另一个数据自上而下流入乘累加单元，最后进行操作，中间值存储在寄存器之中。）
2. 对于大的矩阵乘法应该怎么做？（分块，计算出分块矩阵值后进行存储）
3. 对于大型矩阵（分块矩阵）你的项目是否做到了 Cache 的优化？你提到了分块矩阵的存储（很遗憾没有，不过可以参考 flash attention 的方式，进行条块化和重计算后通过 HBM 优化）
   建议：项目还要进行优化和深化。

三、深度学习、机器学习系统

1. 你了解 Megatron 吗？（是一个大规模 LLM 训练系统，通过结合数据并行，张量并行，流水线并行的 PTP 混合并行方式来进行的系统。）
2. 介绍一下 Megatron v1，v2 和 v3 是怎么进行优化的。
   megatron v1 主要提出了张量并行的方式来优化 GPU 的内存不足问题。某些模型的权重 + 中间激活值太大无法储存在 GPU 中，因此将他们进行分割，分别储存在不同的节点当中。这样就可以减少不同节点之间的内存不足问题。
   缺陷是没有考虑到 TP 所带来的大量通信开销问题。
   2.1 向量并行一般有哪些方式？（行并行，列并行），为什么采取后者？（具有非线性激活，无法通过简单的线性防止进行分块矩阵计算，因此需要进行列并行处理）
   megatron v2 采用了张量并行，数据并行和流水线并行的方式进行。
   2.2 流水线并行进行了什么优化？（1F1B 交叠方式进行，这样显著减少了运算之间流水线的气泡占比）。
   2.3 工作节点数目和数据并行，张量并行和流水线并行的关系？（右边三个东西的乘积就是所需的工作节点数）
   2.4 microbatch 太大了有什么问题？太小了有什么问题？（microbatch 太大会导致单个节点计算缓慢，增加流水线周期。太小会导致频繁地通信，通信开销增大导致严重的通信开销）
   megatron v3 采用激活重计算。因为我没有时间读完因此直接说了面试官也就没有拷打这一部分 QAQ

四、介绍以下目前的慢节点项目（组里）

1. 检测到慢节点后如何恢复？（搬出了 Falcon 提出的解决办法，4 层级恢复：1.继续观察性能 2.数据重新划分 3.并行拓扑重新划分 4.检查点重启）
2. 怎样才能够进行重新调度？你们有了具体方案吗？（诚实回答目前还在调研中，雏形的想法是通过 kv 的方式简化保存的内容，随后再从检查点中重新恢复。）
3. 对于链路的检测和缓解，你认为应该采取什么方案？（对于拥塞，部署在网络层的全局拥塞感知已经在 Sigcomm14 上提出。通过 clos 两层架构，在叶子结点间传递相对应的拥塞指标进行。第一个是分布式架构才可以正确进行链路调度否则会出现问题（举例说明了 ECMP 性能降级），第二个是网络层可以避免绕开内核栈的问题，降低应用层复杂度）
4. 目前你们将采用怎样的方式进行？（RDMA 传递，绕开内核直接写入内存）

五、有什么想问的问题？（公司目前的研发目标？有自研 teletron（感觉是 megatron 套皮没有什么新的技术在里面），也在多个层级上有进行研究）

六、评价一下自己？（目前自己的知识还比较碎片化，觉得系统的研究需要有完整的成体系的知识，以及更加深刻的了解，此外对于分布式的知识掌握仍然在入门，需要更加细致地了解相关知识）。

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(), nums.end());
        auto check = [&](int mx) -> bool {
            int cnt = 0;
            for(int i = 0; i < nums.size() - 1; i++) {
                if(nums[i+1]-nums[i] <= mx) {
                    cnt++;
                    i++;
                }
            }
            return cnt >= p;
        };
        int left = 0, right = nums.back() - nums[0];
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

class Union {
    public:
    vector<int> parents;
    vector<int> size;
    int n;

    Union(int n):n(n), parents(vector<int>(n)), size(vector<int>(n, 1)) {
        iota(parents.begin(), parents.end(), 0);
    }
    int find(int id) {
        if(parents[id] != id) {
            return find(parents[id]);
        }
        return id;
    }
    void merge(int id1, int id2) {
        int pa1, pa2;
        pa1 = find(id1), pa2 = find(id2);
        if(pa1 == pa2) return;
        else if(size[pa1] < size[pa2]) {
            parents[pa1] = pa2;
            size[pa2] += size[pa1];
        } else {
            parents[pa2] = pa1;
            size[pa1] += size[pa2];
        }
    }
};
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> indices(m*n);       // Tips: No repeat.
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                indices[grid[i][j]] = i*m+j;
            }
        }
        constexpr int dir[4][2] = {{-1, 0},{1, 0},{0, -1},{0, 1}};
        Union u(m*n);
        // Merge.
        int t;
        for(t = 0; t < m*n; t++) {
            int cur = indices[t];
            int cur_i, cur_j;
            cur_i = cur / m, cur_j = cur % m;
            for(int i = 0; i < 4; i++) {
                int new_i = cur_i + dir[i][0], new_j = cur_j + dir[i][1];
                if(new_i >= 0 && new_i < m && new_j >= 0 && new_j < n) {
                    int adj_height = grid[new_i][new_j];
                    if(adj_height <= t) {
                        u.merge(cur, new_i * m + new_j);
                    }
                }
            }
            if(u.find(0) == u.find(m*n - 1)) {
                break;
            }
        }
        return t;
    }
};

// The Dijkstra algorithm.
constexpr int directions[4][2] = {{-1, 0},{1, 0},{0, -1},{0, 1}};
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int N = m * n;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        vector<int> distance(N, INT_MAX);
        distance[0] = grid[0][0];
        pq.emplace(distance[0],0);

        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(dist > distance[cur]) continue;
            // Coordinate decomposition. cur = i * m + j.
            int cur_i = cur / m, cur_j = cur % m;
            for(int i = 0; i < 4; i++) {
                int adj_i = cur_i + directions[i][0];
                int adj_j = cur_j + directions[i][1];
                int adj = adj_i * m + adj_j;
                if(adj_i >= 0 && adj_i < m && adj_j >= 0 && adj_j < n) {
                    int new_dist = max(dist, grid[adj_i][adj_j]);
                    if(distance[adj] > new_dist) {
                        distance[adj] = new_dist;
                        pq.emplace(distance[adj], adj);
                    }
                }
            }
        }
        return distance[N - 1];
    }
};

using ll = long long;
constexpr ll MASK = (1ll << 32) - 1;
class Solution {
    public:
        ll coord2Key(int i, int j) {
            ll key = ((ll)i << 32) | j;
            return key;
        }
        pair<int,int> key2Coord(ll key) {
            int i = key >> 32;
            int j = key & MASK;
            return make_pair(i, j);
        }
        int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
            priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
            unordered_set<ll> visited;
            unordered_map<ll, ll> distance;
            int start_x = start[0], start_y = start[1];
            int target_x = target[0], target_y = target[1];
            ll s = coord2Key(start_x, start_y), t = coord2Key(target_x, target_y);
            distance[s] = 0;
            pq.emplace(0, s);
            while(!pq.empty()) {
                const auto [dist, cur] = pq.top();
                pq.pop();
                if(cur == t) break;
                if(visited.find(cur) != visited.end()) continue;
                visited.insert(cur);
                // Update current point to target.
                const auto & [cur_x, cur_y] = key2Coord(cur);
                if(distance.find(t) == distance.end() || distance[t] > dist + llabs(cur_x - target_x) + llabs(cur_y - target_y)) {
                    distance[t] = dist + llabs(cur_x - target_x) + llabs(cur_y - target_y);
                    pq.emplace(distance[t], t);
                }
                // Update the special roads' ends. start -> cur --- (sp.road) ---> end;
                for(const auto & roads: specialRoads) {
                    ll new_dist = dist + (ll)abs(roads[0] - cur_x) + (ll)abs(roads[1] - cur_y) + roads[4];
                    ll adj = coord2Key(roads[2], roads[3]);
                    if(distance.find(adj) == distance.end() || new_dist < distance[adj]) {
                        distance[adj] = new_dist;
                        pq.emplace(distance[adj],adj);
                    }
                }
            }
            return distance[t];
        }
    };

constexpr int MAXN = 1e4+5;
bool notPrime[MAXN];        // When not prime, mark true.

// Eratosthenes prime number calculation.
int init = []() -> int {
    notPrime[0] = true, notPrime[1] = true;
    for(int i = 2; i < MAXN; i++) {
        if(notPrime[i] == false) {
            for(int j = i * i; j < MAXN; j += i) {
                notPrime[j] = true;
            }
        }
    }
    return 0;
}();    // found all prime number.

auto length = [](int num) -> int {
    int len = 0;
    while(num) {
        num /= 10;
        len++;
    }
    return len;
};

class Solution {
public:
    int minOperations(int n, int m) {
        if(notPrime[n] == false || notPrime[m] == false) {
            return -1;
        }
        int len_n = length(n);
        vector<int> distance(pow(10, len_n), INT_MAX);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.emplace(n, n);
        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(cur == m) return dist;
            if(dist > distance[cur]) continue;
            int ratio = 1;
            for(int digit = cur; digit > 0; digit /= 10) {
                if(digit % 10 < 9) {
                    int adj = cur + ratio;
                    if(notPrime[adj] && distance[adj] > dist + adj) {
                        distance[adj] = dist + adj;
                        pq.emplace(distance[adj],adj);
                    }
                }
                if(digit % 10 > 0) {
                    int adj = cur - ratio;
                    if(notPrime[adj] && distance[adj] > dist + adj) {
                        distance[adj] = dist + adj;
                        pq.emplace(distance[adj],adj);
                    }
                }
                ratio *= 10;
            }
        }
        return -1;
    }
};

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size();
        int n = grid[0].size();
        // vector<vector<int>> dp = vector<vector<int>>(m, vector<int>(n,0));
        int * dp_old = new int [n];
        int * dp_new = new int [n];

        for(int j = 0; j < n; j++) {
            dp_old[j]= grid[0][j];
            dp_new[j] = dp_old[j];
        }

        int ans = INT_MAX / 2;
        for(int i = 1; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int temp = INT_MAX / 2;
                for(int k = 0; k < n; k++) {
                    temp = min(temp, dp_old[k]+moveCost[grid[i-1][k]][j]);
                }
                dp_new[j] = temp + grid[i][j];
                if(i == m-1) ans = min(ans, dp_new[j]);
            }
            int * temp = dp_old;
            dp_old = dp_new;
            dp_new = temp;
        }   
        return ans;
    }
};

constexpr int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};   // Directions in four ways, RLUD.
class Solution {
    vector<vector<int>> memo;
    int m;
    int n;
public:
    int dfs(int x, int y, vector<vector<int>> & mat) {
        if(memo[x][y] != -1) return memo[x][y];                 // Prune the dfs branch.
        memo[x][y] = 1;                                         // Initial value with 1.
        for(int i = 0; i < 4; i++) {
            int nx = x + directions[i][0], ny = y + directions[i][1];
            if(nx >= 0 && nx < m 
                && ny >= 0 && ny < n 
                && mat[nx][ny] > mat[x][y]) {
                memo[x][y] = max(dfs(nx, ny, mat) + 1, memo[x][y]);
            }
        }
        return memo[x][y];
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();

        // Abnormal situation dealing with m,n has 0.
        if(m == 0 || n == 0) {
            return 0;
        }

        memo = vector<vector<int>>(m, vector<int>(n,-1));
        int ans = INT_MIN / 2;

        // DFS started at each coord.
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                ans = max(dfs(i,j,matrix),ans);     
            }
        }

        return ans;
    }
};

class Solution {
public:
    int maxDiff(int num) {
        string s = to_string(num);
        string original = s;
        int minNum = INT_MAX, maxNum = INT_MIN;
        
        for(int x = 0; x <= 9; x++) {
            for(int y = 0; y <= 9; y++) {
                for(int i = 0; i < s.length(); i++) {
                    if(s[i] == '0' + x) {
                        s[i] = '0' + y;
                    }
                }
                if(s[0] != '0' && stoi(s) != 0) {
                    minNum = min(stoi(s), minNum);
                    maxNum = max(stoi(s), maxNum);
                }
                s = original;
            }
        }
        return maxNum - minNum;
    }
};

// Using BFS to find the shortest path with the second shortest path.
class Solution {
public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        // Step 1: Build graph here.
        vector<vector<int>> graph(n+1);
        for(const auto edge: edges) {
            int u = edge[0], v = edge[1];
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
        }
        // Step 2: function that get the next time.
        auto step = [&](int curTime) -> int {
            int round = curTime / change;           // Whether it is green or not. % 2 == 0: green;
            if(round % 2 == 1) {
                return (round + 1) * change + time; // next green light + edge weight.
            }
            return curTime + time;
        };
        // Step 3: BFS for 0-1 shortest path.
        vector<vector<int>> distance(2, vector<int>(n+1, INT_MAX));    // distance[0] -> shortest;
        queue<pair<int,int>> q;     // 0-1 BFS using queue is OK;
        q.emplace(0, 1);
        distance[0][1] = 0;
        while(!q.empty()) {
            const auto [dist, cur] = q.front();
            q.pop();
            for(const auto & adj: graph[cur]) {
                int next_time = step(dist);     // Calculate new time.
                if(distance[0][adj] > next_time) {
                    distance[0][adj] = next_time;
                    q.emplace(next_time, adj);
                } else if(distance[0][adj] < next_time && distance[1][adj] > next_time) {
                    distance[1][adj] = next_time;
                    q.emplace(next_time, adj);
                }
            }
        } 
        return distance[1][n];
    }
};

using pii = pair<int,int>;
class Solution {
public:
    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
        if (edges.size() < n - 1) {
            return -1;
        }
        vector<vector<pii>> graph(n);
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[v].emplace_back(u, w);
        }
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        vector<int> distance(n, INT_MAX);
        pq.emplace(0, 0);
        distance[0] = 0;
        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(dist > distance[cur]) continue;
            for(const auto & [adj, w]: graph[cur]) {
                if(distance[adj] > max(dist, w)) {
                    distance[adj] = max(dist, w);
                    pq.emplace(distance[adj], adj);
                }
            }
        }
        int ans = *max_element(distance.begin(), distance.end());
        return ans == INT_MAX ? -1 : ans;
    }
};

using pii = pair<int,int>;
class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        vector<vector<pii>> graph(n);
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1], cost = edge[2] + 1;   // move will be more than 1.
            graph[u].emplace_back(v, cost);
            graph[v].emplace_back(u, cost);
        }
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.emplace(0, 0);
        vector<int> distance(n, INT_MAX);
        distance[0] = 0;
        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(distance[cur] < dist) continue;
            for(const auto & [adj, w]: graph[cur]) {
                if(distance[adj] > dist + w) {
                    distance[adj] = dist + w;
                    pq.emplace(dist + w, adj);
                }
            }
        }
        int ans = 0;
        for(const auto & dist: distance) {
            if(dist <= maxMoves) ans++;     // Calculate two endpoints.
        }
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            int u_dist = max(0, maxMoves - distance[u]);
            int v_dist = max(0, maxMoves - distance[v]);
            ans += min(u_dist + v_dist, w);
        }
        return ans;
    }
};

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        vector<int> prefix_min(nums.size(), INT_MAX);
        prefix_min[0] = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            prefix_min[i] = min(prefix_min[i-1], nums[i]);
        }
        int max_diff = -1;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] == prefix_min[i-1]) continue;
            max_diff = max(nums[i]-prefix_min[i-1], max_diff);
        }
        return max_diff;
    }
};

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> f(n, vector<int>(n, INT_MAX));
        for(int i = 0; i < n; i++) {
            f[i][i] = 0;
        }
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            f[u][v] = w;
            f[v][u] = w;
        }
        for(int k = 0; k < n; k++) {
            for(int u = 0; u < n; u++) {
                if(f[u][k] == INT_MAX) continue;    // Avoid overflow;
                for(int v = 0; v < n; v++) {
                    if(f[k][v] == INT_MAX) continue;
                    f[u][v] = min(f[u][v], f[u][k] + f[k][v]);
                }
            }
        }
        vector<int> candidate(n, 0);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(f[i][j] <= distanceThreshold) {
                    candidate[i]++;
                }
            }
        }
        int min_index = 0, min_city = INT_MAX;
        for(int i = 0; i < n; i++) {
            if(candidate[i] <= min_city) {
                min_index = i;
                min_city = candidate[i];
            }
            // cout << candidate[i] << ' ';
        }
        return min_index;
    }
};

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        using ll = long long;
        ll f[26][26];
        int n = 26;
        for(int i = 0; i < n; i++) {
            memset(f[i], 0x7f, sizeof(ll) * n);
            f[i][i] = 0;
        }
        for(int i = 0; i < cost.size(); i++) {
            ll u = original[i] - 'a', v = changed[i] - 'a', w = cost[i];
            f[u][v] = min(w, f[u][v]);
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                if(f[i][k] == 0x7f7f7f7f7f7f7f7f) continue;
                for(int j = 0; j < n; j++) {
                    if(f[k][j] == 0x7f7f7f7f7f7f7f7f) continue;
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
        ll ans = 0;
        if(source.length() != target.length()) return -1;
        for(int i = 0; i < source.length(); i++) {
            int src = source[i] - 'a', tgt = target[i] - 'a';
            ll cost = f[src][tgt];
            if(cost == 0x7f7f7f7f7f7f7f7f) return -1;
            ans += cost;
        }
        return ans;
    }
};

class Solution {
public:
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        int **f = new int * [n];
        int **graph = new int * [n];
        // iterate over the subset.
        for(int i = 0; i < n; i++) {
            graph[i] = new int [n];
            f[i] = new int [n];
            memset(graph[i], 0x7f, sizeof(int) * n);
            memset(f[i], 0x7f, sizeof(int) * n);
            graph[i][i] = 0;
            f[i][i] = 0;
        }
        for(const auto & edge: roads) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u][v] = min(w, graph[u][v]);
            graph[v][u] = min(w, graph[v][u]);
        }
        
        int ans = 0;
        for(int subset = 0; subset < (1 << n); subset++) {
            // copy the viable f.
            for(int i = 0; i < n; i++) {
                if((subset >> i) & 1) {
                    for(int j = 0; j < n; j++) {
                        f[i][j] = graph[i][j];
                    }
                }
            }
            for(int k = 0; k < n; k++) {
                if(((subset >> k) & 1) == 0) continue;
                for(int u = 0; u < n; u++) {
                    if(f[u][k] == 0x7f7f7f7f || ((subset >> u) & 1) == 0) continue;
                    for(int v = 0; v < n; v++) {
                        if(f[k][v] == 0x7f7f7f7f) continue;
                        f[u][v] = min(f[u][v], f[u][k] + f[k][v]);
                    }
                }
            }
            bool flag = true;
            for (int i = 0; i < n; i++) {
                if (((subset >> i) & 1) == 0) continue;
                for (int j = 0; j < i; j++) {
                    if ((subset >> j) & 1 && f[i][j] > maxDistance) {
                        flag = false;
                        break;
                    }
                }
                if(!flag) break;
            }
            if(!flag) continue;
            ans += 1;
        }
        return ans;
    }
};