# P3116 [USACO15JAN] Meeting Time S ## 题目描述 $\texttt{Bessie}$ 和她的妹妹 $\texttt{Elsie}$ 想从粮仓去她们最喜欢的田地，也就是能够使她们一起从粮仓离开，并且能同一时间到达的田地。 这个农场是由 $N$ 块 $(1\leq N\leq 100)$ 编号为 $1\cdots N$ 的田地构成的，第一块田地就是粮仓，并且第 $N$ 块田地是她们最喜欢的田地。 这个农场建在山的一边，所以，如果 $X < Y$ 的话则满足第 $X$ 块田地的高度要高于第 $Y$ 块田地的高度。在这之中，有 $M$ 条交错纵横的路径将不同的田地连接起来。 不过，显而易见的是，因为每条路都太陡了，所以这些小路只能沿着从高到低的方向走。例如，一条连接第 $5$ 块田地和 $8$ 块田地的小路只能沿着 $5\to 8$ 的方向走，而不能沿着其他方向，因为那样会成为上坡路。每两块田地最多只能有一条路径相连接，所以一定有 $M \leq \dfrac{N(N-1)}{2}$。 有可能的是，$\texttt{Bessie}$ 和 $\texttt{Elsie}$ 两个人走同一条小路会耗费不同的时间；比如，通过同一条小路，$\texttt{Bessie}$ 可能会耗费 $10$ 个单位的时间，而 $\texttt{Elsie}$ 会耗费 $20$ 个单位的时间。 此外，$\texttt{Bessie}$ 和 $\texttt{Elsie}$ 只会在通过连接两块田地的小路时耗费时间——因为她们太匆忙了，在穿过田地时不会耗费任何时间，也从来不在任何地方停下来等待。 现在，请你判断出，能够满足使 $\texttt{Bessie}$ 和 $\texttt{Elsie}$ 同时出发并且同时到达她们喜欢的田地的最短的时间。 ## 输入格式 第一行输入 $N$ 和 $M$，中间用空格分开。 接下来的 $M$ 行，每行有四个整数 $A,B,C,D$，其中，$A$ 和$B(A<B)$ 代表着两块用这条小路连接的田地，$C$ 代表 $\texttt{Bessie}$ 通过这条小路的时间，而 $D$ 代表 $\texttt{Elsie}$ 通过这条小路的时间。$C$ 和 $D$ 均在 $1\cdots100$ 的范围之内。 ## 输出格式 一个整数，输出的是能够使两人同时出发并且同时到达目的地的最短时间，如果没有满足条件的答案，则输出 `IMPOSSIBLE`。 ## 输入输出样例 #1 ### 输入 #1 ``` 3 3 1 3 1 2 1 2 1 2 2 3 1 2 ``` ### 输出 #1 ``` 2 ``` ## 说明/提示 $\texttt{Bessie}$ 在每一条路都比 $\texttt{Elsie}$ 快两倍。 如果 $\texttt{Bessie}$ 经过 $1\to 2\to 3$ 的路线，$\texttt{Elsie}$ 经过 $1\to 3$ 的路线，他们可以同时到达。c++code

<think>嗯，我现在得仔细看看这个题目。题目是说Bessie和她的妹妹Elsie要从粮仓（1号田地）出发，同时到达最喜欢的田地（N号）。她们走不同的路径，每条路径两个人的时间可能不同。我们的任务是找到她们同时到达的最短总时间，如果不可能就输出IMPOSSIBLE。 首先，我需要理解题目的结构。田地是编号1到N的，且X<Y的话，X的高度比Y高，所以所有的路径都是只能从编号小的到大的，也就是只能下坡。所以，整个图应该是一个有向无环图（DAG），因为不会有环，编号只能递增。这样的话，处理路径的时候可能需要拓扑排序或者动态规划的方法？ 接下来，问题是要让两个人的总时间相同，并且找到这样的最短时间。那么，我需要考虑两个人的路径可能不同，但总时间相同的情况下，求最小的那个时间。 那怎么处理两个人的时间呢？可能的思路是，对于每个可能的节点，记录两个人到达这个节点的时间的可能值，然后找到在终点N的时候，时间相同的最小值。比如，可以用动态规划的方法，对于每个节点，维护Bessie和Elsie到达这里的时间的可能组合，然后逐步更新到终点。 不过，这样的话，时间和空间可能会很大。因为假设每个节点可能的Bessie时间和Elsie时间的组合很多，尤其是当N是100的时候，这样的组合可能指数级增长。所以，需要考虑优化方法。 另一个思路是，分别计算两个人从起点到终点的所有可能时间，然后找到两个时间集合的交集中的最小值。比如，先计算Bessie所有可能的到终点的时间，再计算Elsie的所有可能的，然后找两者的共同时间中最小的那个。这个方法的话，如何高效计算所有可能的时间呢？ 但是，这样的做法是否可行呢？假设每个路径的时间总和可能有不同的值，对于每个节点，我们可以维护一个集合，记录到达该节点的可能时间。然后，用类似BFS或者动态规划的方式，不断更新这些时间。例如，对于Bessie来说，到达某个节点的时间等于到达前驱节点的时间加上这条边的Bessie的时间。类似地处理Elsie的情况。 这样，当处理到终点时，我们会有两个集合，分别是Bessie和Elsie的可能到达时间。然后，找这两个集合的交集的最小值。如果有交集的话，取最小值；否则IMPOSSIBLE。 那问题是如何高效地维护这些可能的时间集合。对于每个节点来说，可能有不同的路径到达，导致不同的时间。对于Bessie和Elsie，每个节点的到达时间可能有多个值。比如，节点i的Bessie时间集合和Elsie时间集合。 然后，对于每个节点i，我们可以用两个数组或集合来维护：一个存储Bessie到达i的所有可能时间，另一个存储Elsie到达i的所有可能时间。这样，在处理每条边的时候，比如从a到b的边，Bessie的时间是c，那么对于b的Bessie时间集合来说，可以加上a的Bessie时间集合中的每个元素加上c。同样的方式处理Elsie的情况。 这种方法可能会比较高效，特别是当使用动态规划的方式逐步构建每个节点的可能时间集合。 接下来，如何处理这些集合？比如，可以使用数组或者哈希集合来存储到达每个节点的可能时间。然后，对于每个节点，我们按拓扑顺序处理，这样可以确保在处理a到b的边时，a的所有可能时间已经被计算完毕。 那如何确定拓扑顺序呢？因为所有的边都是从小的节点号到大的，所以节点1到N的顺序本身就是一个拓扑排序的顺序。所以，我们可以按照节点1、2、3...N的顺序来处理每个节点，这样在处理节点a时，所有能到达a的边（即所有起点小于a的边）已经被处理过了。 这样，处理每个节点时，遍历所有入边（也就是所有以该节点为终点的边），然后根据这些边的前驱节点的可能时间，加上当前边的时间，来更新当前节点的可能时间集合。 例如，对于节点b，假设有一个边a→b。那么，对于Bessie来说，到达b的时间可以是到达a的时间加上这条边的c。所以，我们遍历所有a的前驱节点的可能时间，然后加上c，将这些时间添加到b的Bessie时间集合中。同样的方式处理Elsie的情况。 这样，我们可以按节点顺序从小到大处理，逐步构建每个节点的可能时间集合。 然后，当处理到节点N时，我们得到Bessie的可能时间集合和Elsie的可能时间集合，求它们的交集的最小值。 现在的问题是，如何高效地维护这些集合，避免重复元素，并且能够快速合并。例如，可以使用动态规划中的状态压缩，或者使用哈希集合（如C++的unordered_set或set）来存储到达每个节点的可能时间。这样，每次添加时间的时候，自动去重。 比如，在C++中，可以使用两个数组，每个元素是一个set结构。例如，对于每个节点i，bessie_time[i]是一个set，保存所有可能的Bessie到达i的时间；同理，elsie_time[i]保存Elsie到达i的时间。 初始时，节点1的Bessie和Elsie时间都是0。然后，按照节点顺序处理每个节点。对于每个节点a，遍历所有出边a→b。然后，对于每个这样的边，将a的Bessie时间集合中的每个元素加上c，加入到b的Bessie时间集合中。同样的，将a的Elsie时间集合中的每个元素加上d，加入到b的Elsie时间集合中。 但这样会不会有问题？比如，可能存在多条路径到达同一个节点，导致不同的时间。例如，对于节点b，可能有不同的a，不同的边，导致不同的时间。这个时候，必须将所有可能的路径的时间都考虑进去，才能得到完整的可能时间集合。 因此，这种处理方式是正确的，因为对于每个边a→b，处理a的所有可能时间，加上边的时间，得到到达b的时间的可能值。这些值会被合并到b的时间集合中。然后，当处理更大的节点时，前面的节点的集合已经被完全处理了。 这样的方法的时间复杂度如何？假设每个节点的集合中的时间数量是有限的。例如，假设每条边的时间最多是100，那么对于节点i来说，最大的可能时间总和是100*100（因为每个边最多被走一次？或者可能多次？但题目中的图是DAG，所以每条边只能被走一次。因为路径只能是严格递增的节点顺序，所以每个节点最多出现在路径中一次。因此，每条边最多被走一次。所以，对于N=100的节点，每条边的权值是100，那么总的最大时间是100*100=1e4。所以，每个节点的集合中的时间最多是1e4，这应该是可以接受的。 但实际情况中，当边数较多时，可能的时间总和可能更大。例如，如果每条边都是100，路径长度可能有M条边。但题目中M的上限是N(N-1)/2，即对于N=100的话，M是4950条边。那么，总的时间可能达到4950*100=495000。这样的数量级对于set来说还是可以处理的吗？比如，每个节点的集合可能有几千个元素？ 比如，假设每个节点的集合最多有1e5个元素，那么总共有100个节点，每个节点的两个集合总共有2*1e5*100=2e7个元素。这在内存上可能没问题，但处理时间可能较慢。不过，对于题目中的N=100来说，这样的时间复杂度是否能够接受呢？比如，假设每个边都要处理，每个边的处理需要遍历前驱节点的集合中的每个元素。例如，假设每个边处理的时间是O(k)，其中k是前驱节点集合的大小。那么，总的时间复杂度是O(M*k)。如果k平均是1e4的话，M是4950，那么总共有大约5e7次操作，这在C++中是可以通过的，因为每秒大约可以处理1e8次操作。 不过，这样的实现可能需要优化，比如使用有序的集合，或者使用数组来存储可能的时间，并通过动态规划的方式合并。或者，可以用bitset来优化，但时间值的范围可能较大，所以bitset可能不适用。 或者，可以采用动态规划的方式，使用二维数组来记录到达每个节点时，Bessie和Elsie的时间的可能值。但这样的话，二维数组的维度可能太大。比如，假设Bessie的时间可能到5e4，那么二维数组的大小是100 * 5e4，这可能太大。 因此，回到最初的思路，每个节点维护两个集合，存储所有可能的时间。那么，如何处理这些集合？ 在代码实现上，可以用C++的数组，每个元素是一个unordered_set或者set。初始化时，节点1的两个集合都是{0}。然后，对于每个节点a，从小到大处理，遍历所有a的出边a→b。对于每个这样的边，取a的bessie集合中的每个时间t，将t + c添加到b的bessie集合中。同样的，处理elsie的集合。 这里需要注意的是，必须按节点的顺序从小到大处理，以确保当处理到节点a时，a的所有可能的时间已经被完全计算，之后不会再被修改。这样，当处理a的出边时，a的时间集合已经是最终的状态。 例如，在代码中，可以首先将所有边按起点存储。例如，建立一个邻接表，其中adj[a]保存所有从a出发的边。然后，按a从1到N的顺序遍历每个节点。对于每个a，遍历其所有邻接边，处理这些边，并更新对应的终点节点的集合。 这样，每个边只被处理一次，且在处理该边的时候，起点的集合已经是完整的。 现在，考虑具体实现步骤： 1. 读取输入，存储所有边。因为题目中的边的A和B满足A<B，所以邻接表中只需要存储每个a的出边。 2. 初始化两个数组，比如bessie和elsie，每个是一个unordered_set。其中，bessie[1] = {0}, elsie[1] = {0}。其他节点的初始为空集合。 3. 按照节点a从1到N的顺序进行处理： a. 对于每个a，遍历其所有出边（即所有边的起点是a）。 b. 对于每条边a→b，Bessie的时间是c，Elsie的时间是d。 c. 对于b的bessie集合，将当前b的集合合并上a的bessie集合中的每个元素加上c后的结果。 d. 同样处理elsie的集合。 4. 当处理完所有节点后，查看bessie[N]和elsie[N]的交集。如果存在交集，找到最小值；否则输出IMPOSSIBLE。 现在，问题是如何高效地将a的集合元素加上c后，合并到b的集合中。例如，在C++中，可以这样做： 对于每条边a→b： for (auto t : bessie[a]) { bessie[b].insert(t + c); } 这样，将a的所有时间加上c后，插入到b的集合中。同样处理elsie的情况。 但是，这样的方式是否会导致重复插入？例如，如果多个不同的边到达b，那么每次处理这些边的时候，都会将新的时间插入到b的集合中。而使用unordered_set或者set会自动去重，所以不会有重复元素。例如，当不同的路径到达b的时间相同时，集合中只保留一个值。 这样，最终每个节点的集合保存的是所有可能的到达时间，去重后的结果。 这样，在节点N的两个集合的交集的最小值即为所求。 接下来，如何处理这两个集合的交集？例如，在C++中，可以将两个集合中的元素取出来，排序后进行比较。或者，可以将其中一个集合的元素存入一个哈希集合，然后遍历另一个集合的元素，查看是否存在，并记录最小值。 例如，对于Bessie的集合b_set和Elsie的集合 e_set，可以遍历其中一个集合的每个元素，如果这个元素同时存在于另一个集合中，就记录最小值。 这可能在时间上是可行的，特别是当集合的大小不是特别大的情况下。 现在，考虑输入样例的情况： 输入是3 3，有三条边： 1 3 1 2 → 这条边1→3，Bessie用时1，Elsie用时2。 1 2 1 2 → 1→2，B和E的时间都是1和2。 2 3 1 2 → 2→3，B和E的时间都是1和2。 然后，处理节点1： 它的出边是1→3和1→2。 处理边1→3： 对于Bessie来说，bessie[3]插入0+1=1。 Elsie的elsie[3]插入0+2=2. 处理边1→2： bessie[2]插入0+1=1. elsie[2]插入0+2=2. 然后，处理节点2： 它的出边是2→3。 对于这条边，处理Bessie的情况：a=2，c=1。所以，对于bessie[2]中的元素1，加上1得到2。插入到bessie[3]中。所以，bessie[3]现在有1和2。 同样，Elsie的情况：a=2的elsie时间是2，加上d=2，得到4。插入到elsie[3]中。现在，elsie[3]中有2（来自1→3）和4（来自2→3的Elsie路径）。 处理节点3时，没有出边。 最终，bessie[3] = {1, 2}，elsie[3] = {2,4}。两者的交集是2，所以最小值是2，符合样例输出。 这说明上述方法是正确的。 那现在的问题是如何在代码中高效实现这个逻辑。对于每个节点，按顺序处理，然后合并时间。 现在，关于代码的编写： 首先，读取N和M。然后，建立邻接表。每个节点a对应的出边列表。每个边包括b、c、d。 然后，初始化两个数组，bessie和elsie，每个元素是一个unordered_set<int>。或者，也可以使用set<int>，因为有序的集合可能在后面找交集时更高效？ 例如，如果两个集合都是有序的，那么可以用双指针的方法来找交集的最小值。这可能更高效。比如，将两个集合排序后，用两个指针分别遍历，找出最小的共同元素。 所以，可能更高效的方式是使用set，这样元素是自动排序的。 因此，在代码中，每个节点的bessie和elsie集合用set结构来存储，这样插入时会自动排序，且去重。 然后，当处理每条边a→b时，对于每个元素t_b in bessie[a]，将t_b + c插入到bessie[b]中。因为set自动处理重复元素，所以无需担心重复。 这样，在处理节点时，每个节点的bessie和elsie集合保持有序。 最后，当处理完所有节点后，取bessie[N]和elsie[N]的交集的最小值。 现在，如何找交集的最小值？ 将两个有序的集合合并，或者遍历其中一个集合的元素，查看是否存在于另一个集合中。例如，可以遍历bessie[N]中的元素（从小到大），检查是否存在于elsie[N]的集合中。第一个存在的元素即为最小值。 或者，同时遍历两个有序的集合，用双指针的方法。 例如： 指针i指向bessie集合的第一个元素，指针j指向elsie集合的第一个元素。比较两个元素的值。如果相等，即为答案。如果bessie[i] < elsie[j]，则i++。否则j++。直到找到相等的元素，或者遍历完所有元素。 这样的方式时间复杂度是O(n + m)，其中n和m是两个集合的大小。 这样的方式可能更高效，尤其是当两个集合较大时。例如，当集合的大小较大时，哈希查找可能更慢。 比如，在样例中，bessie[N]是{1,2}，elsie[N]是{2,4}。遍历时，第一个元素1比2小，所以i++到2。此时，与j的元素2相等，找到结果。 所以，双指针的方法是正确的。 因此，在代码中，可以将两个集合的元素转换为有序的列表（例如，用vector保存），然后进行双指针遍历。 现在，编写代码的大致步骤： 读取N和M。 构建邻接表：对于每个边，按起点存储。例如，使用一个数组或vector，邻接表的结构是vector<vector<tuple<int, int, int>>> adj(N+1)。其中，每个元素adj[a]保存所有从a出发的边，每个边是一个tuple(b, c, d)。 初始化两个数组，bessie和elsie，每个元素是set<int>类型。例如，bessie[1].insert(0); elsie[1].insert(0); 然后，按照节点a从1到N的顺序进行处理： 对于每个a，遍历其所有邻接边（即adj[a]中的每个元素）： 每个元素是(b, c, d)。 对于Bessie的集合： 遍历bessie[a]中的每个时间t： 将t + c插入到bessie[b]的集合中。 同样，对于Elsie的集合： 遍历elsie[a]中的每个时间t： 将t + d插入到elsie[b]的集合中。 这样处理所有边。 最后，检查bessie[N]和elsie[N]的交集。 如果没有交集，输出IMPOSSIBLE。否则，找到最小的共同元素。 如何高效地找到两个有序集合的交集的最小值？ 将两个集合转换为vector，然后用双指针法： 例如： vector<int> vb(bessie[N].begin(), bessie[N].end()); vector<int> ve(elsie[N].begin(), elsie[N].end()); int i = 0, j = 0; int res = INT_MAX; while (i < vb.size() && j < ve.size()) { if (vb[i] == ve[j]) { res = vb[i]; break; } else if (vb[i] < ve[j]) { i++; } else { j++; } } 如果res被更新，则输出res，否则输出IMPOSSIBLE. 这样，就能找到最小的公共时间。 现在，需要考虑边界情况，例如，当N=1时，输出0？ 题目中，输入的N至少是1吗？题目描述中的输入样例是3，所以可能存在N=1的情况？比如，当粮仓和最喜欢的田地都是1号田地，那么两人不需要移动，总时间是0。此时，输出0。但题目中的输入描述中，可能N>=1？ 所以，代码中应该处理这种情况。例如，当N=1时，直接输出0。 但是，题目中的输入中的M可能为0吗？比如，当N=1时，M必须为0。那么，代码中需要处理这种情况。 但题目中的输入描述中，输入的M可能为0。比如，当N=1时，无法有任何边，所以两人已经在终点，总时间为0。 因此，代码中需要处理N=1的情况，此时直接输出0。 其他情况，例如当N>=2时，需要按照上述方法处理。 这样，在代码中，可以首先判断N是否为1，如果是，直接输出0。否则，按照上述步骤处理。 现在，考虑一些可能的错误情况： 例如，当无法到达N号节点，此时bessie[N]或elsie[N]可能为空。此时，直接输出IMPOSSIBLE。 例如，当两个集合中有一个为空，那么交集必然为空，所以输出IMPOSSIBLE。 因此，在代码中，处理完所有节点后，需要检查这两个集合是否非空。如果其中一个是空的，则直接输出IMPOSSIBLE。否则，再找交集。 综上，代码的步骤是： 1. 处理输入，建立邻接表。 2. 初始化bessie和elsie的集合，设置节点1的时间为0。 3. 按节点顺序处理每个节点的边，更新对应节点的集合。 4. 处理完所有节点后，检查节点N的两个集合是否都非空。 5. 如果至少有一个为空，输出IMPOSSIBLE。 6. 否则，找出两个集合的交集中的最小值，如果存在则输出，否则输出IMPOSSIBLE。 现在，如何测试代码的正确性？ 例如，样例输入中的情况，代码应该输出2。此外，当没有路径到达终点时，输出IMPOSSIBLE。 另一个测试案例，比如当N=2，M=1，边是1→2，B时间1，E时间1。此时，两人都走这条路径，总时间都是1，所以输出1。 或者，当N=2，M=1，边是1→2，B的时间2，E的时间3。那么，两人的集合分别是{2}和{3}，没有交集，输出IMPOSSIBLE。 现在，考虑如何处理节点的处理顺序。例如，必须按节点从小到大处理，确保在处理a的出边时，a的集合已经被完全处理。 在代码中，如果邻接表是按照节点顺序建立的，那么处理节点1到N的顺序是正确的。 现在，编写代码的大致结构： #include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; if (N == 1) { cout << 0 << endl; return 0; } vector<vector<tuple<int, int, int>>> adj(N+1); for (int i=0; i<M; ++i) { int A, B, C, D; cin >> A >> B >> C >> D; adj[A].emplace_back(B, C, D); } vector<set<int>> bessie(N+1), elsie(N+1); bessie[1].insert(0); elsie[1].insert(0); for (int a=1; a<=N; ++a) { for (auto &edge : adj[a]) { int b = get<0>(edge); int c = get<1>(edge); int d = get<2>(edge); // 处理Bessie的路径 for (int t : bessie[a]) { bessie[b].insert(t + c); } // 处理Elsie的路径 for (int t : elsie[a]) { elsie[b].insert(t + d); } } } if (bessie[N].empty() || elsie[N].empty()) { cout << "IMPOSSIBLE" << endl; return 0; } // 找两个集合的交集的最小值 vector<int> vb(bessie[N].begin(), bessie[N].end()); vector<int> ve(elsie[N].begin(), elsie[N].end()); int i=0, j=0; int res = -1; while (i < vb.size() && j < ve.size()) { if (vb[i] == ve[j]) { res = vb[i]; break; } else if (vb[i] < ve[j]) { i++; } else { j++; } } if (res != -1) { cout << res << endl; } else { cout << "IMPOSSIBLE" << endl; } return 0; } 现在，测试样例输入： 输入： 3 3 1 3 1 2 1 2 1 2 2 3 1 2 处理顺序： 节点1的出边是1→3和1→2。 处理节点1的边： 对于边1→3，Bessie的bessie[3]插入0+1=1，Elsie的elsie[3]插入0+2=2. 对于边1→2，Bessie的bessie[2]插入0+1=1，Elsie的elsie[2]插入0+2=2. 节点2的出边是2→3. 处理节点2的边： 对于边2→3，Bessie的bessie[3]插入1+1=2，Elsie的elsie[3]插入2+2=4. 此时，bessie[3]是{1,2}，elsie[3]是{2,4}. 双指针遍历时，i=0，vb[0]=1，j=0，ve[0]=2。1<2，i++到1。此时，vb[1]=2，等于ve[j]=2，得到结果2. 输出正确。 另一个测试案例，比如N=2，M=1，边是1 2 2 3： bessie[2] = {2}, elsie[2] = {3}。交集为空，输出IMPOSSIBLE. 所以，代码是正确的。 现在，考虑可能的优化： 例如，当处理到某个节点时，如果其集合已经很大，可以提前剪枝，例如，如果某个时间已经比当前找到的最优解大，则可以忽略。但是，这可能无法实现，因为最优解可能还没有找到。所以，可能无法剪枝。 此外，可以使用优先队列的方式，每次处理最小的时间，以便一旦找到公共的时间就可以立即返回。但这种方法可能较为复杂，因为需要同时处理两个人的路径。 综上，当前的代码应该可以正确处理所有情况。</think>要解决这个问题，我们需要找到Bessie和Elsie从粮仓（节点1）同时出发并同时到达最喜欢的田地（节点N）的最短时间。以下是详细的解决方案： ### 方法思路 1. **图的结构分析**：题目中的田地构成一个有向无环图（DAG），所有路径只能从编号较小的节点到较大的节点。 2. **动态规划+集合存储**：使用动态规划的思想，为每个节点维护两个集合，分别记录Bessie和Elsie到达该节点的所有可能时间。 3. **拓扑顺序处理**：按节点编号从小到大处理，确保在处理当前节点的出边时，所有前驱节点的可能时间已被完全计算。 4. **交集查找**：在终点节点N，找到Bessie和Elsie的时间集合的交集中的最小值。 ### 解决代码 ```cpp #include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; if (N == 1) { cout << 0 << endl; return 0; } vector<vector<tuple<int, int, int>>> adj(N + 1); for (int i = 0; i < M; ++i) { int A, B, C, D; cin >> A >> B >> C >> D; adj[A].emplace_back(B, C, D); } vector<set<int>> bessie(N + 1), elsie(N + 1); bessie[1].insert(0); elsie[1].insert(0); for (int a = 1; a <= N; ++a) { for (auto &edge : adj[a]) { int b = get<0>(edge); int c = get<1>(edge); int d = get<2>(edge); for (int t : bessie[a]) { bessie[b].insert(t + c); } for (int t : elsie[a]) { elsie[b].insert(t + d); } } } if (bessie[N].empty() || elsie[N].empty()) { cout << "IMPOSSIBLE" << endl; return 0; } vector<int> vb(bessie[N].begin(), bessie[N].end()); vector<int> ve(elsie[N].begin(), elsie[N].end()); int i = 0, j = 0; int res = -1; while (i < vb.size() && j < ve.size()) { if (vb[i] == ve[j]) { res = vb[i]; break; } else if (vb[i] < ve[j]) { i++; } else { j++; } } if (res != -1) { cout << res << endl; } else { cout << "IMPOSSIBLE" << endl; } return 0; } ``` ### 代码解释 1. **输入处理**：读取节点数和边数，构建邻接表存储图结构。 2. **初始化集合**：节点1的初始时间为0。 3. **动态规划处理**：按节点顺序处理每条边，更新到达各节点的可能时间集合。 4. **结果判断**：检查终点的时间集合是否存在交集，找到最小公共时间或输出不可行。 该方法利用动态规划和集合操作，确保高效地找到最短的同步到达时间。时间复杂度主要取决于节点数和边数，能够在合理时间内处理题目给定的约束条件。