Graph
Topological Sort
Dynamic Programming
Shortest Path
Heap (Priority Queue)
Description
There is an undirected weighted connected graph. You are given a positive integer n
which denotes that the graph has n
nodes labeled from 1
to n
, and an array edges
where each edges[i] = [ui , vi , weighti ]
denotes that there is an edge between nodes ui
and vi
with weight equal to weighti
.
A path from node start
to node end
is a sequence of nodes [z0 , z1 , z2 , ..., zk ]
such that z0 = start
and zk = end
and there is an edge between zi
and zi+1
where 0 <= i <= k-1
.
The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x)
denote the shortest distance of a path between node n
and node x
. A restricted path is a path that also satisfies that distanceToLastNode(zi ) > distanceToLastNode(zi+1 )
where 0 <= i <= k-1
.
Return the number of restricted paths from node 1
to node n
. Since that number may be too large, return it modulo 109 + 7
.
Example 1:
Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output: 3
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5
Example 2:
Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output: 1
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 --> 3 --> 7.
Constraints:
1 <= n <= 2 * 104
n - 1 <= edges.length <= 4 * 104
edges[i].length == 3
1 <= ui , vi <= n
ui != vi
1 <= weighti <= 105
There is at most one edge between any two nodes.
There is at least one path between any two nodes.
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 class Solution :
def countRestrictedPaths ( self , n : int , edges : List [ List [ int ]]) -> int :
@cache
def dfs ( i ):
if i == n :
return 1
ans = 0
for j , _ in g [ i ]:
if dist [ i ] > dist [ j ]:
ans = ( ans + dfs ( j )) % mod
return ans
g = defaultdict ( list )
for u , v , w in edges :
g [ u ] . append (( v , w ))
g [ v ] . append (( u , w ))
q = [( 0 , n )]
dist = [ inf ] * ( n + 1 )
dist [ n ] = 0
mod = 10 ** 9 + 7
while q :
_ , u = heappop ( q )
for v , w in g [ u ]:
if dist [ v ] > dist [ u ] + w :
dist [ v ] = dist [ u ] + w
heappush ( q , ( dist [ v ], v ))
return dfs ( 1 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 class Solution {
private static final int INF = Integer . MAX_VALUE ;
private static final int MOD = ( int ) 1e9 + 7 ;
private List < int []>[] g ;
private int [] dist ;
private int [] f ;
private int n ;
public int countRestrictedPaths ( int n , int [][] edges ) {
this . n = n ;
g = new List [ n + 1 ] ;
for ( int i = 0 ; i < g . length ; ++ i ) {
g [ i ] = new ArrayList <> ();
}
for ( int [] e : edges ) {
int u = e [ 0 ] , v = e [ 1 ] , w = e [ 2 ] ;
g [ u ] . add ( new int [] { v , w });
g [ v ] . add ( new int [] { u , w });
}
PriorityQueue < int []> q = new PriorityQueue <> (( a , b ) -> a [ 0 ] - b [ 0 ] );
q . offer ( new int [] { 0 , n });
dist = new int [ n + 1 ] ;
f = new int [ n + 1 ] ;
Arrays . fill ( dist , INF );
Arrays . fill ( f , - 1 );
dist [ n ] = 0 ;
while ( ! q . isEmpty ()) {
int [] p = q . poll ();
int u = p [ 1 ] ;
for ( int [] ne : g [ u ] ) {
int v = ne [ 0 ] , w = ne [ 1 ] ;
if ( dist [ v ] > dist [ u ] + w ) {
dist [ v ] = dist [ u ] + w ;
q . offer ( new int [] { dist [ v ] , v });
}
}
}
return dfs ( 1 );
}
private int dfs ( int i ) {
if ( f [ i ] != - 1 ) {
return f [ i ] ;
}
if ( i == n ) {
return 1 ;
}
int ans = 0 ;
for ( int [] ne : g [ i ] ) {
int j = ne [ 0 ] ;
if ( dist [ i ] > dist [ j ] ) {
ans = ( ans + dfs ( j )) % MOD ;
}
}
f [ i ] = ans ;
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 using pii = pair < int , int > ;
class Solution {
public :
const int inf = INT_MAX ;
const int mod = 1e9 + 7 ;
vector < vector < pii >> g ;
vector < int > dist ;
vector < int > f ;
int n ;
int countRestrictedPaths ( int n , vector < vector < int >>& edges ) {
this -> n = n ;
g . resize ( n + 1 );
dist . assign ( n + 1 , inf );
f . assign ( n + 1 , -1 );
dist [ n ] = 0 ;
for ( auto & e : edges ) {
int u = e [ 0 ], v = e [ 1 ], w = e [ 2 ];
g [ u ]. emplace_back ( v , w );
g [ v ]. emplace_back ( u , w );
}
priority_queue < pii , vector < pii > , greater < pii >> q ;
q . emplace ( 0 , n );
while ( ! q . empty ()) {
auto [ _ , u ] = q . top ();
q . pop ();
for ( auto [ v , w ] : g [ u ]) {
if ( dist [ v ] > dist [ u ] + w ) {
dist [ v ] = dist [ u ] + w ;
q . emplace ( dist [ v ], v );
}
}
}
return dfs ( 1 );
}
int dfs ( int i ) {
if ( f [ i ] != -1 ) return f [ i ];
if ( i == n ) return 1 ;
int ans = 0 ;
for ( auto [ j , _ ] : g [ i ]) {
if ( dist [ i ] > dist [ j ]) {
ans = ( ans + dfs ( j )) % mod ;
}
}
f [ i ] = ans ;
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 const inf = math . MaxInt32
const mod = 1e9 + 7
type pair struct {
first int
second int
}
var _ heap . Interface = ( * pairs )( nil )
type pairs [] pair
func ( a pairs ) Len () int { return len ( a ) }
func ( a pairs ) Less ( i int , j int ) bool {
return a [ i ]. first < a [ j ]. first || a [ i ]. first == a [ j ]. first && a [ i ]. second < a [ j ]. second
}
func ( a pairs ) Swap ( i int , j int ) { a [ i ], a [ j ] = a [ j ], a [ i ] }
func ( a * pairs ) Push ( x any ) { * a = append ( * a , x .( pair )) }
func ( a * pairs ) Pop () any { l := len ( * a ); t := ( * a )[ l - 1 ]; * a = ( * a )[: l - 1 ]; return t }
func countRestrictedPaths ( n int , edges [][] int ) int {
g := make ([] pairs , n + 1 )
for _ , e := range edges {
u , v , w := e [ 0 ], e [ 1 ], e [ 2 ]
g [ u ] = append ( g [ u ], pair { v , w })
g [ v ] = append ( g [ v ], pair { u , w })
}
dist := make ([] int , n + 1 )
f := make ([] int , n + 1 )
for i := range dist {
dist [ i ] = inf
f [ i ] = - 1
}
dist [ n ] = 0
h := make ( pairs , 0 )
heap . Push ( & h , pair { 0 , n })
for len ( h ) > 0 {
u := heap . Pop ( & h ).( pair ). second
for _ , ne := range g [ u ] {
v , w := ne . first , ne . second
if dist [ v ] > dist [ u ] + w {
dist [ v ] = dist [ u ] + w
heap . Push ( & h , pair { dist [ v ], v })
}
}
}
var dfs func ( int ) int
dfs = func ( i int ) int {
if f [ i ] != - 1 {
return f [ i ]
}
if i == n {
return 1
}
ans := 0
for _ , ne := range g [ i ] {
j := ne . first
if dist [ i ] > dist [ j ] {
ans = ( ans + dfs ( j )) % mod
}
}
f [ i ] = ans
return ans
}
return dfs ( 1 )
}
Solution 2
Python3 Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution :
def countRestrictedPaths ( self , n : int , edges : List [ List [ int ]]) -> int :
g = defaultdict ( list )
for u , v , w in edges :
g [ u ] . append (( v , w ))
g [ v ] . append (( u , w ))
dist = [ inf ] * ( n + 1 )
dist [ n ] = 0
q = [( 0 , n )]
mod = 10 ** 9 + 7
while q :
_ , u = heappop ( q )
for v , w in g [ u ]:
if dist [ v ] > dist [ u ] + w :
dist [ v ] = dist [ u ] + w
heappush ( q , ( dist [ v ], v ))
arr = list ( range ( 1 , n + 1 ))
arr . sort ( key = lambda i : dist [ i ])
f = [ 0 ] * ( n + 1 )
f [ n ] = 1
for i in arr :
for j , _ in g [ i ]:
if dist [ i ] > dist [ j ]:
f [ i ] = ( f [ i ] + f [ j ]) % mod
return f [ 1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 class Solution {
private static final int INF = Integer . MAX_VALUE ;
private static final int MOD = ( int ) 1e9 + 7 ;
public int countRestrictedPaths ( int n , int [][] edges ) {
List < int []>[] g = new List [ n + 1 ] ;
Arrays . setAll ( g , k -> new ArrayList <> ());
for ( int [] e : edges ) {
int u = e [ 0 ] , v = e [ 1 ] , w = e [ 2 ] ;
g [ u ] . add ( new int [] { v , w });
g [ v ] . add ( new int [] { u , w });
}
PriorityQueue < int []> q = new PriorityQueue <> (( a , b ) -> a [ 0 ] - b [ 0 ] );
q . offer ( new int [] { 0 , n });
int [] dist = new int [ n + 1 ] ;
Arrays . fill ( dist , INF );
dist [ n ] = 0 ;
while ( ! q . isEmpty ()) {
int [] p = q . poll ();
int u = p [ 1 ] ;
for ( int [] ne : g [ u ] ) {
int v = ne [ 0 ] , w = ne [ 1 ] ;
if ( dist [ v ] > dist [ u ] + w ) {
dist [ v ] = dist [ u ] + w ;
q . offer ( new int [] { dist [ v ] , v });
}
}
}
int [] f = new int [ n + 1 ] ;
f [ n ] = 1 ;
Integer [] arr = new Integer [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
arr [ i ] = i + 1 ;
}
Arrays . sort ( arr , ( i , j ) -> dist [ i ] - dist [ j ] );
for ( int i : arr ) {
for ( int [] ne : g [ i ] ) {
int j = ne [ 0 ] ;
if ( dist [ i ] > dist [ j ] ) {
f [ i ] = ( f [ i ] + f [ j ] ) % MOD ;
}
}
}
return f [ 1 ] ;
}
}
GitHub