当前位置：网站首页>2022-07-31: Given a graph with n points and m directed edges, you can use magic to turn directed edges into undirected edges, such as directed edges from A to B, with a weight of 7.After casting the m
2022-07-31: Given a graph with n points and m directed edges, you can use magic to turn directed edges into undirected edges, such as directed edges from A to B, with a weight of 7.After casting the m
2022-08-01 03:41:00 【F greatly architects of the day】
2022-07-31：给出一个有n个点,m条有向边的图,
You can have the ability to cast magic,Keep to the edge,Into the undirected edge,
比如A到B的有向边,权重为7.After the magic,A和BBy the side to reach each other's price is7.
求,Permission to cast a spell,1到n的最短路,如果不能到达,输出-1.
n为点数, 每条边用(a,b,v)表示,含义是a到b的这条边,权值为v.
点的数量 <= 10^5,边的数量 <= 2 * 10^5,1 <= 边的权值 <= 10^6.
来自网易.
答案2022-07-31：
Unit of shortest path algorithm.dijkstra算法.
Point expansion,边扩充.
代码用rust编写.代码如下：
use rand::Rng;
fn main() {
let nn: i32 = 20;
let vv: i32 = 30;
let test_time: i32 = 2000;
println!("测试开始");
for _ in 0..test_time {
let n = rand::thread_rng().gen_range(0, nn) + 2;
let mut roads = random_roads(n, vv);
let ans1 = min1(n, &mut roads);
let ans2 = min2(n, &mut roads);
if ans1 != ans2 {
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
println!("roads = {:?}", roads);
println!("出错了!");
break;
}
}
println!("测试结束");
}
// 为了测试
// Relatively violent solution
// Try each of the directed edge,Becomes an undirected edge,And then run adijkstra算法
// It must be the best answer
fn min1(n: i32, roads: &mut Vec<Vec<i32>>) -> i32 {
let mut ans = 2147483647;
for i in 0..roads.len() as i32 {
let mut graph: Vec<Vec<Vec<i32>>> = vec![];
for _ in 0..=n {
graph.push(vec![]);
}
graph[roads[i as usize][1] as usize].push(vec![roads[i as usize][0], roads[i as usize][2]]);
for r in roads.iter() {
graph[r[0] as usize].push(vec![r[1], r[2]]);
}
ans = get_min(ans, dijkstra1(n, &mut graph));
}
return if ans == 2147483647 {
-1 } else {
ans };
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
fn dijkstra1(n: i32, graph: &mut Vec<Vec<Vec<i32>>>) -> i32 {
let mut heap: Vec<Vec<i32>> = vec![];
let mut visited: Vec<bool> = vec![];
for _ in 0..n + 1 {
visited.push(false);
}
heap.push(vec![1, 0]);
let mut ans = 2147483647;
while heap.len() > 0 {
heap.sort_by(|a, b| (b[1].cmp(&a[1])));
let cur = heap.pop().unwrap();
if cur[0] == n {
ans = cur[1];
break;
}
if visited[cur[0] as usize] {
continue;
}
visited[cur[0] as usize] = true;
for edge in graph[cur[0] as usize].iter() {
let to = edge[0];
let weight = edge[1];
if !visited[to as usize] {
heap.push(vec![to, cur[1] + weight]);
}
}
}
return ans;
}
// 最优解
// 时间复杂度O(N * logN)
// N <= 2 * 10^5
fn min2(n: i32, roads: &mut Vec<Vec<i32>>) -> i32 {
let mut graph: Vec<Vec<Vec<i32>>> = vec![];
for _ in 0..=n {
graph.push(vec![]);
}
for r in roads.iter() {
graph[r[0] as usize].push(vec![0, r[1], r[2]]);
graph[r[1] as usize].push(vec![1, r[0], r[2]]);
}
let mut heap: Vec<Vec<i32>> = vec![];
let mut visited: Vec<Vec<bool>> = vec![];
for i in 0..2 {
visited.push(vec![]);
for _ in 0..n + 1 {
visited[i as usize].push(false);
}
}
// a -> 0,a 1,a
// boolean[] visted = new boolean[n+1]
// visted[i] == true 去过了！Pop up from the queue！Later don't touch！
// visted[i] == false 没去过！Pop up from the queue for the first time！当前要处理！
// 0,1,0 -> There is no magic road before,当前来到1号出发点,代价是0
heap.push(vec![0, 1, 0]);
let mut ans = 2147483647;
while heap.len() > 0 {
heap.sort_unstable_by(|a, b|b[2].cmp(&a[2]));
let cur = heap.pop().unwrap();
if visited[cur[0] as usize][cur[1] as usize] {
continue;
}
visited[cur[0] as usize][cur[1] as usize] = true;
if cur[1] == n {
ans = get_min(ans, cur[2]);
if visited[0][n as usize] && visited[1][n as usize] {
break;
}
}
for edge in graph[cur[1] as usize].iter() {
// 当前来到cur
// Did before through the magic path：cur[0] == 0 ,没走过！cur[0] = 1, 走过了
// The current point to what,cur[1],点编号！
// What is the total cost before？cur[2]
// cur,往下,能走的,Where all the way？
// The current road,叫edge
// The current road,If magic way！edge[0] = 0 , Is not a magic way
// edge[0] == 1,Is a magic way
// cur[0] + edge[0] == 0
// 路 ：0 5 20
// 当前路,Is not a magic way,To the point is5号点,This weight is20
// 路 ：1 7 13
// 当前路,Is a magic way,To the point is7号点,This weight is13
if cur[0] + edge[0] == 0 {
if !visited[0][edge[1] as usize] {
heap.push(vec![0, edge[1], cur[2] + edge[2]]);
}
}
// cur[0] + edge[0] == 1
// 0 1
// 1 0
if cur[0] + edge[0] == 1 {
if !visited[1][edge[1] as usize] {
heap.push(vec![1, edge[1], cur[2] + edge[2]]);
}
}
// 1 1 == 2
}
}
return if ans == 2147483647 {
-1 } else {
ans };
}
// 为了测试
fn random_roads(n: i32, v: i32) -> Vec<Vec<i32>> {
let m = rand::thread_rng().gen_range(0, n * (n - 1) / 2) + 1;
let mut roads: Vec<Vec<i32>> = vec![];
for i in 0..m {
roads.push(vec![]);
for _ in 0..3 {
roads[i as usize].push(0);
}
}
for i in 0..m {
roads[i as usize][0] = rand::thread_rng().gen_range(0, n) + 1;
roads[i as usize][1] = rand::thread_rng().gen_range(0, n) + 1;
roads[i as usize][2] = rand::thread_rng().gen_range(0, v) + 1;
}
return roads;
}
执行结果如下：
代码用go编写.代码如下：
package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
func main() {
rand.Seed(time.Now().Unix())
N := 20
V := 30
testTime := 2000
fmt.Println("测试开始")
for i := 0; i < testTime; i++ {
n := rand.Intn(N) + 2
roads := randomRoads(n, V)
ans1 := min1(n, roads)
ans2 := min2(n, roads)
if ans1 != ans2 {
fmt.Println("出错了!")
fmt.Println("roads = ", roads)
fmt.Println("ans1 = ", ans1)
fmt.Println("ans2 = ", ans2)
fmt.Println("-----------")
break
}
}
fmt.Println("测试结束")
}
// 为了测试
// Relatively violent solution
// Try each of the directed edge,Becomes an undirected edge,And then run adijkstra算法
// It must be the best answer
func min1(n int, roads [][]int) int {
ans := 2147483647
for i := 0; i < len(roads); i++ {
graph := make([][][]int, 0)
for j := 0; j <= n; j++ {
graph = append(graph, make([][]int, 0))
}
graph[roads[i][1]] = append(graph[roads[i][1]], []int{
roads[i][0], roads[i][2]})
for _, r := range roads {
graph[r[0]] = append(graph[r[0]], []int{
r[1], r[2]})
}
ans = getMin(ans, dijkstra1(n, graph))
}
if ans == 2147483647 {
return -1
} else {
return ans
}
}
func getMin(a, b int) int {
if a < b {
return a
} else {
return b
}
}
func dijkstra1(n int, graph [][][]int) int {
heap0 := make([][]int, 0)
visited := make([]bool, n+1)
heap0 = append(heap0, []int{
1, 0})
ans := 2147483647
for len(heap0) > 0 {
sort.Slice(heap0, func(i, j int) bool {
a := heap0[i]
b := heap0[j]
return a[1] < b[1]
})
cur := heap0[0]
heap0 = heap0[1:]
if cur[0] == n {
ans = cur[1]
break
}
if visited[cur[0]] {
continue
}
visited[cur[0]] = true
for _, edge := range graph[cur[0]] {
to := edge[0]
weight := edge[1]
if !visited[to] {
heap0 = append(heap0, []int{
to, cur[1] + weight})
}
}
}
return ans
}
// 最优解
// 时间复杂度O(N * logN)
// N <= 2 * 10^5
func min2(n int, roads [][]int) int {
graph := make([][][]int, 0)
for j := 0; j <= n; j++ {
graph = append(graph, make([][]int, 0))
}
for _, r := range roads {
graph[r[0]] = append(graph[r[0]], []int{
0, r[1], r[2]})
graph[r[1]] = append(graph[r[1]], []int{
1, r[0], r[2]})
}
heap0 := make([][]int, 0)
visited := make([][]bool, 2)
for i := 0; i < 2; i++ {
visited[i] = make([]bool, n+1)
}
// a -> 0,a 1,a
// boolean[] visted = new boolean[n+1]
// visted[i] == true 去过了！Pop up from the queue！Later don't touch！
// visted[i] == false 没去过！Pop up from the queue for the first time！当前要处理！
// 0,1,0 -> There is no magic road before,当前来到1号出发点,代价是0
heap0 = append(heap0, []int{
0, 1, 0})
ans := 2147483647
for len(heap0) > 0 {
sort.Slice(heap0, func(i, j int) bool {
a := heap0[i]
b := heap0[j]
return a[2] < b[2]
})
cur := heap0[0]
heap0 = heap0[1:]
if visited[cur[0]][cur[1]] {
continue
}
visited[cur[0]][cur[1]] = true
if cur[1] == n {
ans = getMin(ans, cur[2])
if visited[0][n] && visited[1][n] {
break
}
}
for _, edge := range graph[cur[1]] {
// 当前来到cur
// Did before through the magic path：cur[0] == 0 ,没走过！cur[0] = 1, 走过了
// The current point to what,cur[1],点编号！
// What is the total cost before？cur[2]
// cur,往下,能走的,Where all the way？
// The current road,叫edge
// The current road,If magic way！edge[0] = 0 , Is not a magic way
// edge[0] == 1,Is a magic way
// cur[0] + edge[0] == 0
// 路 ：0 5 20
// 当前路,Is not a magic way,To the point is5号点,This weight is20
// 路 ：1 7 13
// 当前路,Is a magic way,To the point is7号点,This weight is13
if cur[0]+edge[0] == 0 {
if !visited[0][edge[1]] {
heap0 = append(heap0, []int{
0, edge[1], cur[2] + edge[2]})
}
}
// cur[0] + edge[0] == 1
// 0 1
// 1 0
if cur[0]+edge[0] == 1 {
if !visited[1][edge[1]] {
heap0 = append(heap0, []int{
1, edge[1], cur[2] + edge[2]})
}
}
// 1 1 == 2
}
}
if ans == 2147483647 {
return -1
} else {
return ans
}
}
// 为了测试
func randomRoads(n, v int) [][]int {
m := rand.Intn(int(n*(n-1)/2)) + 1
roads := make([][]int, m)
for i := 0; i < m; i++ {
roads[i] = make([]int, 3)
}
for i := 0; i < m; i++ {
roads[i][0] = rand.Intn(n) + 1
roads[i][1] = rand.Intn(n) + 1
roads[i][2] = rand.Intn(v) + 1
}
return roads
}
执行结果如下：
边栏推荐
猜你喜欢
button去除黑框
![[cellular automata] based on matlab interface aggregation cellular automata simulation [including Matlab source code 2004]](/img/7b/831998e19591ce8b90cfb2eefae0d4.png)
[cellular automata] based on matlab interface aggregation cellular automata simulation [including Matlab source code 2004]
Game Security 03: A Simple Explanation of Buffer Overflow Attacks
MySQL4
IDEA does not recognize the module (there is no blue square in the lower right corner of the module)
opencv 缩小放大用哪种插值更好??
黑客到底可以厉害到什么程度？
Error using ts-node
Hackers can how bad to what degree?
IDEA modifies the annotation font
随机推荐
Basic use of vim - command mode
TypeScript simplifies running ts-node
IDEA 找不到或无法加载主类 或 Module “*“ must not contain source root “*“ The root already belongs to module “*“
剑指offer专项突击版第16天
Software Testing Interview (3)
手写二叉查找树及测试
Input input box cursor automatically jumps to the last bug after the previous input
How to write a high-quality digital good article recommendation
Guys, MySQL cdc source recycles replication slave and r in incremental process
Dart 命名参数语法
button去除黑框
Unknown Bounded Array
By CSDN, torn
Introduction to Oracle
test
MySQL3
MySQL4
＜JDBC＞ 批量插入 的四种实现方式：你真的get到了吗？
Open source project site must-have & communication area function
The fledgling Xiao Li's 114th blog project notes: Wisdom cloud intelligent flower watering device combat (3) - basic Demo implementation