用数据结构c++处理给一个 ( 1 ≤ ≤ 1 0 6 ) n(1≤n≤10 6 ) 个点 ( 1 ≤ ≤ 1 0 6 ) m(1≤m≤10 6 ) 条边的无向图，求 � s 到 � t 的最短路的长度。 数据保证， � s 出发可以到达 � t。 Input 请从 stdin 读入。注意，输入可能很大 ( > 10 M B ) (>10MB)。 第一行为四个正整数 � , � , � , � n,m,s,t。 第二行起 � m 行，每行三个非负整数 � � , � � , � � ( 0 ≤ � � ≤ 1 ) u i ​ ,v i ​ ,w i ​ (0≤w i ​ ≤1)，表示从 u i ​ 到 v i ​ 有一条权值为 w i ​ 的无向边。 Output

这道题可以使用 Dijkstra 算法来解决。由于输入可能非常大，我们需要使用一些技巧来优化空间和时间复杂度。

首先，我们可以使用邻接表来存储图，而不是邻接矩阵，这样可以大大减少空间占用。

其次，由于边的权值只有 0 和 1，我们可以将它们分别存储在两个不同的链表中。这样，我们可以在遍历邻接表时只考虑权值为 0 或 1 的边，而不需要额外的判断。

最后，由于我们只需要求出从 s 到 t 的最短路长度，而不需要具体的路径，因此我们可以使用一个数组来记录已经找到的最短路长度，而不需要使用一个二维数组来记录每个点到其他点的距离。

下面是代码实现：