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：给出一个有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
}

执行结果如下：

---

左神java代码