当前位置：网站首页>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
}
执行结果如下：
边栏推荐
- 2. ＃ 代码注释
- 【 Make YOLO Great Again 】 YOLOv1 v7 full range with large parsing (Neck)
- Which interpolation is better for opencv to zoom in and out??
- Hackers can how bad to what degree?
- How to write a high-quality digital good article recommendation
- 解决IDEA默认情况下新建文件时，右击，new，没有XML文件的问题
- HCIP(15)
- Solve the problem that when IDEA creates a new file by default, right-click, new, there is no XML file
- The 16th day of the special assault version of the sword offer
- The fledgling Xiao Li's 114th blog project notes: Wisdom cloud intelligent flower watering device combat (3) - basic Demo implementation
猜你喜欢
MySQL3
Solve the problem that when IDEA creates a new file by default, right-click, new, there is no XML file
Unknown Bounded Array
Talking about hardware device computing storage and data interaction
IDEA does not recognize the module (there is no blue square in the lower right corner of the module)
How is the tree structure of the device tree reflected?
Hackers can how bad to what degree?
Input input box cursor automatically jumps to the last bug after the previous input
ARM cross compilation
【入门教程】Rollup模块打包器整合
随机推荐
这个地图绘制工具太赞了，推荐~~
手写二叉查找树及测试
Device tree - conversion from dtb format to struct device node structure
opencv 缩小放大用哪种插值更好??
Flutter “Hello world“ 程代码
Message Queuing Message Storage Design (Architecture Camp Module 8 Jobs)
Unity's primary method for implementing PlanarReflection under the BuildIn rendering pipeline
Soft Exam Senior System Architect Series: Basic Knowledge of Information Systems
项目越写越大，我是这样做拆分的
The IDEA can't find or unable to load The main class or Module "*" must not contain The source root "*" The root already belongs to The Module "*"
简单易用的任务队列-beanstalkd
初出茅庐的小李第114篇博客项目笔记之机智云智能浇花器实战(3)-基础Demo实现
lua entry case combat 123DIY
pdb药物综合数据库
Replacing the Raspberry Pi Kernel
Talking about hardware device computing storage and data interaction
MySQL4
The fledgling Xiao Li's 113th blog project notes: Wisdom cloud smart flower watering device combat (2) - basic Demo implementation
软件测试周刊（第82期）：其实所有纠结做选择的人心里早就有了答案，咨询只是想得到内心所倾向的选择。
彻底关闭Chrome浏览器更新及右上角的更新提示