给定一个 n 个点 m 条边的不含重边和自环的无向图。 点的编号为 1∼n ，边的编号为 1∼m 。 在 t=0 时刻，你位于 1 号点。 你的任务是尽可能早的抵达 n 号点。 第 i 条边连接点 ai 和点 bi ，通过此边需要花费的时间为 ci 。 在整个移动过程中，你只有在整数时刻才能离开某一点前往另一点。 此外，第 i 个点有 ki 个禁止离开时刻。 在每个点的禁止离开时刻，你无法离开该点前往其它点。 请你计算抵达 n 号点的最早可能时刻。 输入格式 第一行包含两个整数 n,m 。 接下来 m 行，其中第 i 行包含三个整数 ai,bi,ci ，表示第 i 条边连接点 ai 和 bi ，通过此边需要花费的时间为 ci 。 接下来 n 行，其中第 i 行首先包含一个整数 ki ，表示第 i 个点有 ki 个禁止离开时刻，随后包含 ki 个互不相同的升序排序的整数 tij ，表示所有禁止离开时刻。 输出格式 一个整数，表示抵达 n 号点的最早可能时刻。 如果无法抵达 n 号点，则输出 -1。 数据范围 前 4 个测试点满足 2≤n≤4 。 所有测试点满足 2≤n≤105 ，0≤m≤105 ，1≤ai,bi≤n ，ai≠bi ，1≤ci≤104 ，0≤ki≤105 ，0≤tij<109 ，所有 ki 相加之和不超过 105 。

这是一个算法问题，我可以回答。这道题可以用 Dijkstra 算法求解，具体步骤如下：

1. 初始化距离数组 dist，将所有点的距离初始化为正无穷，将起点 1 的距离初始化为 0。

2. 初始化堆，将起点 1 加入堆中。

3. 不断从堆中取出距离最小的点 u，遍历 u 的所有邻居 v，如果 dist[u]+w(u,v) 的值比 dist[v] 小，则更新 dist[v] 的值，并将 v 加入堆中。

4. 重复步骤 3 直到堆为空或者堆顶为终点 n。

5. 如果 dist[n] 的值为正无穷，则表示无法到达终点，否则 dist[n] 的值即为最短时间。

需要注意的是，在遍历邻居时需要判断当前时间是否为禁止离开时刻，如果是则不能移动。

时间复杂度为 O(mlogn)，其中 m 为边数，n 为点数。

相关问题

给定一个n个顶点（1到n编号）的无向图，以及若干条边，请对其构造邻接矩阵。

好的，根据您的要求，我会为您构造邻接矩阵。

假设给定的无向图有n个顶点，那么我们可以用一个n × n的矩阵来表示它的邻接矩阵。对于每条边 (u, v)，我们在矩阵的第u行第v列和第v行第u列上标记为1，表示这两个顶点之间有一条边。如果两个顶点之间没有边，则在对应的位置标记为0。

以下是构造邻接矩阵的示例代码（假设给定的边存储在一个列表中，每个元素为一个二元组(u, v)表示一条边）：

n = 10  # 顶点数
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (2, 5), (3, 5), (4, 1)]  # 边列表

adj_matrix = [[0] * n for _ in range(n)]  # 初始化邻接矩阵为全0

for u, v in edges:
    adj_matrix[u-1][v-1] = 1  # 标记边的两个端点
    adj_matrix[v-1][u-1] = 1

print(adj_matrix)  # 输出邻接矩阵

希望能帮到您！

给定一个n个顶点（1到n编号）的无向图，以及若干条边，请对其构造邻接矩阵。c语言

好的，以下是在C语言中构造邻接矩阵的示例代码（假设给定的边存储在一个二维数组中，每一行表示一条边，两个元素分别为边的两个顶点编号）：

#include <stdio.h>

#define MAX_N 1000

int adj_matrix[MAX_N][MAX_N];  // 定义邻接矩阵

int main() {
    int n, m;  // n为顶点数，m为边数
    scanf("%d%d", &n, &m);

    // 初始化邻接矩阵为全0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj_matrix[i][j] = 0;
        }
    }

    // 读入边并标记邻接矩阵
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj_matrix[u-1][v-1] = 1;  // 标记边的两个端点
        adj_matrix[v-1][u-1] = 1;
    }

    // 输出邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", adj_matrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

希望能帮到您！