河南省城市建设网站,简易的网站模板,无锡做网站好,平潭县建设局网站LeetCode
到达目的地的方案数
题目链接#xff1a;1976. 到达目的地的方案数 - 力扣#xff08;LeetCode#xff09;
题目描述
你在一个城市里#xff0c;城市由 n 个路口组成#xff0c;路口编号为 0 到 n - 1 #xff0c;某些路口之间有 双向 道路。输入保证你可以…LeetCode
到达目的地的方案数
题目链接1976. 到达目的地的方案数 - 力扣LeetCode
题目描述
你在一个城市里城市由 n 个路口组成路口编号为 0 到 n - 1 某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口且任意两个路口之间最多有一条路。
给你一个整数 n 和二维整数数组 roads 其中 roads[i] [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大将结果对 109 7 取余 后返回。
示例 1 输入n 7, roads [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
输出4
解释从路口 0 出发到路口 6 花费的最少时间是 7 分钟。
四条花费 7 分钟的路径分别为
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6示例 2
输入n 2, roads [[1,0,10]]
输出1
解释只有一条从路口 0 到路口 1 的路花费 10 分钟。提示
1 n 200n - 1 roads.length n * (n - 1) / 2roads[i].length 30 ui, vi n - 11 timei 109ui ! vi任意两个路口之间至多有一条路。从任意路口出发你能够到达其他任意路口。
思路
Dijkstra 算法
代码
C
class Solution {
public:int countPaths(int n, vectorvectorint roads) {vectorvectorlong long g(n,vectorlong long(n,LLONG_MAX / 2));for(auto r : roads){int x r[0], y r[1], d r[2];g[x][y] d;g[y][x] d;}vectorlong long dis(n, LLONG_MAX / 2);dis[0] 0;vectorint f(n),done(n);f[0] 1;while(true){int x -1;for(int i 0; i n; i){if(!done[i] (x 0 || dis[i] dis[x])){x i;}}if(x n - 1){return f[n - 1];}done[x] true; // 最短路长度已确定无法变得更小for(int y 0; y n; y){long long new_dis dis[x] g[x][y];if(new_dis dis[y]){dis[y] new_dis;f[y] f[x];} else if(new_dis dis[y]){f[y] (f[y] f[x]) % 1000000007;}}}}
};Java
class Solution {public int countPaths(int n, int[][] roads) {long[][] g new long[n][n]; // 邻接矩阵for (long[] row : g) {Arrays.fill(row, Long.MAX_VALUE / 2); // 防止溢出}for (int[] r : roads) {int x r[0];int y r[1];int d r[2];g[x][y] d;g[y][x] d;}long[] dis new long[n];Arrays.fill(dis, 1, n, Long.MAX_VALUE / 2);int[] f new int[n];f[0] 1;boolean[] done new boolean[n];while (true) {int x -1;for (int i 0; i n; i) {if (!done[i] (x 0 || dis[i] dis[x])) {x i;}}if (x n - 1) {// 不可能找到比 dis[n-1] 更短或者一样短的最短路了注意本题边权都是正数return f[n - 1];}done[x] true; // 最短路长度已确定无法变得更小for (int y 0; y n; y) { // 尝试更新 x 的邻居的最短路long newDis dis[x] g[x][y];if (newDis dis[y]) {// 就目前来说最短路必须经过 xdis[y] newDis;f[y] f[x];} else if (newDis dis[y]) {// 和之前求的最短路一样长f[y] (f[y] f[x]) % 1_000_000_007;}}}}
}
