本文共 1519 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要找到所有满足特定条件的树形结构，计算这些结构的数量，并对结果取模。具体来说，我们需要确保每个房间到第1号房间的最短路径等于实际路径长度。

方法思路

解决代码

import sysfrom collections import dequedef main():    MOD = 2**31 - 1    n, m = map(int, sys.stdin.readline().split())    edges = []    adj = [[] for _ in range(n + 1)]    for _ in range(m):        x, y, l = map(int, sys.stdin.readline().split())        edges.append((x, y, l))        adj[x].append((y, l))        adj[y].append((x, l))        INF = 10**18    D = [INF] * (n + 1)    D[1] = 0    visited = [False] * (n + 1)    q = deque()    q.append(1)    visited[1] = True        while q:        u = q.popleft()        for (v, l) in adj[u]:            if not visited[v]:                if D[u] + l < D[v]:                    D[v] = D[u] + l                    visited[v] = True                    q.append(v)        indegree = [0] * (n + 1)    for x, y, l in edges:        if x > y:            x, y = y, x        if D[x] + l == D[y]:            indegree[y] += 1        if D[y] + l == D[x]:            indegree[x] += 1        ans = 1    for i in range(2, n + 1):        ans = (ans * indegree[i]) % MOD        print(ans)if __name__ == "__main__":    main()

代码解释

通过这种方法，我们可以高效地解决问题，并得到正确的结果。

转载地址：http://ijufk.baihongyu.com/