Skip to content

Commit c34bf88

Browse files
YangFongYangFong
committed
feat: add solutions to lc problem: No.2492
No.2492.Minimum Score of a Path Between Two Cities
1 parent 37ae413 commit c34bf88

File tree

5 files changed

+177
-16
lines changed

5 files changed

+177
-16
lines changed

‎solution/2400-2499/2492.Minimum Score of a Path Between Two Cities/README.md

Lines changed: 62 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -332,14 +332,14 @@ func min(a, b int) int {
332332
### **JavaScript**
333333

334334
```js
335-
var minScore = function(n, roads) {
335+
var minScore = function (n, roads) {
336336
// 构建点到点的映射表
337-
const graph = Array.from({length: n + 1}, () => new Map());
337+
const graph = Array.from({ length: n + 1 }, () => new Map());
338338
for (let [u, v, w] of roads) {
339339
graph[u].set(v, w);
340340
graph[v].set(u, w);
341341
}
342-
342+
343343
// DFS
344344
const vis = new Array(n).fill(false);
345345
let ans = Infinity;
@@ -349,13 +349,70 @@ var minScore = function(n, roads) {
349349
ans = Math.min(ans, w);
350350
if (!vis[v]) dfs(v);
351351
}
352-
}
352+
};
353353
dfs(1);
354-
354+
355355
return ans;
356356
};
357357
```
358358

359+
### **TypeScript**
360+
361+
```ts
362+
function minScore(n: number, roads: number[][]): number {
363+
const vis = new Array(n + 1).fill(false);
364+
const g = Array.from({ length: n + 1 }, () => []);
365+
for (const [a, b, v] of roads) {
366+
g[a].push([b, v]);
367+
g[b].push([a, v]);
368+
}
369+
let ans = Infinity;
370+
const dfs = (i: number) => {
371+
if (vis[i]) {
372+
return;
373+
}
374+
vis[i] = true;
375+
for (const [j, v] of g[i]) {
376+
ans = Math.min(ans, v);
377+
dfs(j);
378+
}
379+
};
380+
dfs(1);
381+
return ans;
382+
}
383+
```
384+
385+
### **Rust**
386+
387+
```rust
388+
impl Solution {
389+
fn dfs(i: usize, mut ans: i32, g: &Vec<Vec<(usize, i32)>>, vis: &mut Vec<bool>) -> i32 {
390+
if vis[i] {
391+
return ans;
392+
}
393+
vis[i] = true;
394+
for (j, v) in g[i].iter() {
395+
ans = ans.min(*v.min(&Self::dfs(*j, ans, g, vis)));
396+
}
397+
ans
398+
}
399+
400+
pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
401+
let n = n as usize;
402+
let mut vis = vec![false; n + 1];
403+
let mut g = vec![Vec::new(); n + 1];
404+
for road in roads.iter() {
405+
let a = road[0] as usize;
406+
let b = road[1] as usize;
407+
let v = road[2];
408+
g[a].push((b, v));
409+
g[b].push((a, v));
410+
}
411+
Self::dfs(1, i32::MAX, &g, &mut vis)
412+
}
413+
}
414+
```
415+
359416
### **...**
360417

361418
```

‎solution/2400-2499/2492.Minimum Score of a Path Between Two Cities/README_EN.md

Lines changed: 62 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -306,14 +306,14 @@ func min(a, b int) int {
306306
### **JavaScript**
307307

308308
```js
309-
var minScore = function(n, roads) {
309+
var minScore = function (n, roads) {
310310
// 构建点到点的映射表
311-
const graph = Array.from({length: n + 1}, () => new Map());
311+
const graph = Array.from({ length: n + 1 }, () => new Map());
312312
for (let [u, v, w] of roads) {
313313
graph[u].set(v, w);
314314
graph[v].set(u, w);
315315
}
316-
316+
317317
// DFS
318318
const vis = new Array(n).fill(false);
319319
let ans = Infinity;
@@ -323,13 +323,70 @@ var minScore = function(n, roads) {
323323
ans = Math.min(ans, w);
324324
if (!vis[v]) dfs(v);
325325
}
326-
}
326+
};
327327
dfs(1);
328-
328+
329329
return ans;
330330
};
331331
```
332332

333+
### **TypeScript**
334+
335+
```ts
336+
function minScore(n: number, roads: number[][]): number {
337+
const vis = new Array(n + 1).fill(false);
338+
const g = Array.from({ length: n + 1 }, () => []);
339+
for (const [a, b, v] of roads) {
340+
g[a].push([b, v]);
341+
g[b].push([a, v]);
342+
}
343+
let ans = Infinity;
344+
const dfs = (i: number) => {
345+
if (vis[i]) {
346+
return;
347+
}
348+
vis[i] = true;
349+
for (const [j, v] of g[i]) {
350+
ans = Math.min(ans, v);
351+
dfs(j);
352+
}
353+
};
354+
dfs(1);
355+
return ans;
356+
}
357+
```
358+
359+
### **Rust**
360+
361+
```rust
362+
impl Solution {
363+
fn dfs(i: usize, mut ans: i32, g: &Vec<Vec<(usize, i32)>>, vis: &mut Vec<bool>) -> i32 {
364+
if vis[i] {
365+
return ans;
366+
}
367+
vis[i] = true;
368+
for (j, v) in g[i].iter() {
369+
ans = ans.min(*v.min(&Self::dfs(*j, ans, g, vis)));
370+
}
371+
ans
372+
}
373+
374+
pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
375+
let n = n as usize;
376+
let mut vis = vec![false; n + 1];
377+
let mut g = vec![Vec::new(); n + 1];
378+
for road in roads.iter() {
379+
let a = road[0] as usize;
380+
let b = road[1] as usize;
381+
let v = road[2];
382+
g[a].push((b, v));
383+
g[b].push((a, v));
384+
}
385+
Self::dfs(1, i32::MAX, &g, &mut vis)
386+
}
387+
}
388+
```
389+
333390
### **...**
334391

335392
```

‎solution/2400-2499/2492.Minimum Score of a Path Between Two Cities/Solution.js

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
1-
var minScore = function(n, roads) {
1+
var minScore = function (n, roads) {
22
// 构建点到点的映射表
3-
const graph = Array.from({length: n + 1}, () => new Map());
3+
const graph = Array.from({ length: n + 1 }, () => new Map());
44
for (let [u, v, w] of roads) {
55
graph[u].set(v, w);
66
graph[v].set(u, w);
77
}
8-
8+
99
// DFS
1010
const vis = new Array(n).fill(false);
1111
let ans = Infinity;
@@ -15,8 +15,8 @@ var minScore = function(n, roads) {
1515
ans = Math.min(ans, w);
1616
if (!vis[v]) dfs(v);
1717
}
18-
}
18+
};
1919
dfs(1);
20-
20+
2121
return ans;
22-
};
22+
};

‎solution/2400-2499/2492.Minimum Score of a Path Between Two Cities/Solution.rs

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
impl Solution {
2+
fn dfs(i: usize, mut ans: i32, g: &Vec<Vec<(usize, i32)>>, vis: &mut Vec<bool>) -> i32 {
3+
if vis[i] {
4+
return ans;
5+
}
6+
vis[i] = true;
7+
for (j, v) in g[i].iter() {
8+
ans = ans.min(*v.min(&Self::dfs(*j, ans, g, vis)));
9+
}
10+
ans
11+
}
12+
13+
pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
14+
let n = n as usize;
15+
let mut vis = vec![false; n + 1];
16+
let mut g = vec![Vec::new(); n + 1];
17+
for road in roads.iter() {
18+
let a = road[0] as usize;
19+
let b = road[1] as usize;
20+
let v = road[2];
21+
g[a].push((b, v));
22+
g[b].push((a, v));
23+
}
24+
Self::dfs(1, i32::MAX, &g, &mut vis)
25+
}
26+
}

‎solution/2400-2499/2492.Minimum Score of a Path Between Two Cities/Solution.ts

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
function minScore(n: number, roads: number[][]): number {
2+
const vis = new Array(n + 1).fill(false);
3+
const g = Array.from({ length: n + 1 }, () => []);
4+
for (const [a, b, v] of roads) {
5+
g[a].push([b, v]);
6+
g[b].push([a, v]);
7+
}
8+
let ans = Infinity;
9+
const dfs = (i: number) => {
10+
if (vis[i]) {
11+
return;
12+
}
13+
vis[i] = true;
14+
for (const [j, v] of g[i]) {
15+
ans = Math.min(ans, v);
16+
dfs(j);
17+
}
18+
};
19+
dfs(1);
20+
return ans;
21+
}

0 commit comments

Comments
 (0)