2022-07-31:给出一个有n个点,m条有向边的图, 你可以施展魔法,把有向边,变成无向边

2022-07-31:给出一个有n个点,m条有向边的图,
你可以施展魔法,把有向边,变成无向边,
比如A到B的有向边,权重为7。施展魔法之后,A和B通过该边到达彼此的代价都是7。
求,允许施展一次魔法的情况下,1到n的最短路,如果不能到达,输出-1。
n为点数, 每条边用(a,b,v)表示,含义是a到b的这条边,权值为v。
点的数量 <= 10^5,边的数量 <= 2 * 10^5,1 <= 边的权值 <= 10^6。
来自网易。

答案2022-07-31:

单元路径最短算法。dijkstra算法。
点扩充,边扩充。

代码用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!("测试结束");
}

// 为了测试
// 相对暴力的解
// 尝试每条有向边,都变一次无向边,然后跑一次dijkstra算法
// 那么其中一定有最好的答案
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 去过了!从队列里弹出来过了!以后别碰了!
    // visted[i] == false 没去过!第一次从队列里弹出来!当前要处理!
    // 0,1,0 -> 之前没有走过魔法路,当前来到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
            // 之前有没有走过魔法路径:cur[0] == 0 ,没走过!cur[0] = 1, 走过了
            // 当前来到的点是啥,cur[1],点编号!
            // 之前的总代价是啥?cur[2]
            // cur,往下,能走的,所有的路在哪?
            // 当前的路,叫edge
            // 当前的路,是不是魔法路!edge[0] = 0 , 不是魔法路
            // edge[0] == 1,是魔法路
            // cur[0] + edge[0] == 0
            // 路 :0 5 20
            // 当前路,不是魔法路,去往的点是5号点,该路权重是20
            // 路 :1 7 13
            // 当前路,是魔法路,去往的点是7号点,该路权重是13
            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("测试结束")
}

// 为了测试
// 相对暴力的解
// 尝试每条有向边,都变一次无向边,然后跑一次dijkstra算法
// 那么其中一定有最好的答案
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 去过了!从队列里弹出来过了!以后别碰了!
    // visted[i] == false 没去过!第一次从队列里弹出来!当前要处理!
    // 0,1,0 -> 之前没有走过魔法路,当前来到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
            // 之前有没有走过魔法路径:cur[0] == 0 ,没走过!cur[0] = 1, 走过了
            // 当前来到的点是啥,cur[1],点编号!
            // 之前的总代价是啥?cur[2]
            // cur,往下,能走的,所有的路在哪?
            // 当前的路,叫edge
            // 当前的路,是不是魔法路!edge[0] = 0 , 不是魔法路
            // edge[0] == 1,是魔法路
            // cur[0] + edge[0] == 0
            // 路 :0 5 20
            // 当前路,不是魔法路,去往的点是5号点,该路权重是20
            // 路 :1 7 13
            // 当前路,是魔法路,去往的点是7号点,该路权重是13
            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代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!