2022-07-31：给出一个有n个点，m条有向边的图， 你可以施展魔法，把有向边，变成无向边
10 / 0 / 创建于 1年前
moonfdd 的个人博客
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
}
执行结果如下：
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：