go实现
题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为非负值。
请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示1号点到n号点的最短距离。
如果路径不存在,则输出-1。
数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于0,且不超过10000。
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
算法1 ,采用go的自带的heap实现
package main
import (
"bufio"
"container/heap"
"fmt"
"os"
"strconv"
"strings"
)
const N int = 1e6 + 10
var (
h [N]int
e [N]int
ne [N]int
idx int
w [N]int
dist [N]int
n, m int
st [N]bool
)
func add(a, b, c int) {
e[idx] = b
ne[idx] = h[a]
w[idx] = c
h[a] = idx
idx++
}
func readline(r *bufio.Reader) []int {
s, _ := r.ReadString('\n')
ss := strings.Fields(s)
res := make([]int, len(ss))
for i, v := range ss {
res[i], _ = strconv.Atoi(v)
}
return res
}
func dijkstra() int {
for i := 0; i < N; i++ {
dist[i] = 0x3f3f3f3f
}
dist[1] = 0
// 堆优化
var q PriorityQueue
// q :=make(PriorityQueue,0,n)
heap.Push(&q, &pair{first: 0, second: 1})
for q.Len() > 0 {
t := heap.Pop(&q)
if v, ok := t.(*pair); ok {
distance := v.first
ver := v.second
if st[ver]{
continue
}
st[ver] = true
for i := h[ver]; i != -1; i = ne[i] {
j := e[i]
if dist[j] > distance+w[i] {
dist[j] = distance + w[i]
heap.Push(&q, &pair{first: dist[j], second: j})
}
}
}
}
if dist[n] == 0x3f3f3f3f {
return -1
}
return dist[n]
}
//采用自带的堆heap,要实现若干接口
type pair struct {
first int
second int
}
type PriorityQueue []*pair
func (pq *PriorityQueue) Push(x interface{}) {
if v, ok := x.(*pair); ok {
*pq = append(*pq, v)
}
}
func (pq *PriorityQueue) Pop() interface{} {
n := len(*pq)
x := (*pq)[n-1]
*pq = (*pq)[:n-1]
return x
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].first < pq[j].first
}
func main() {
fmt.Scanf("%d%d", &n, &m)
for i := 0; i < N; i++ {
h[i] = -1
}
r := bufio.NewReader(os.Stdin)
for m > 0 {
m--
in := readline(r)
a, b, z := in[0], in[1], in[2]
add(a, b, z)
}
fmt.Println(dijkstra())
}
时间复杂度Omlog(n)
算法2 手写堆heap实现
此方法没有完全通过测试,值通过了10/12
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
const N int=1e6+10
var (
h [N]int
ph [N]int
hp [N]int
size int
hh [N]int
e[N]int
ne[N]int
w[N]int
idx int
dist [N]int
n,m int
)
func down(u int) {
t:=u
if 2*u<=size && h[2*u]<h[t]{
t = 2*u
}
if 2*u+1<=size && h[2*u+1]<h[t]{
t = 2*u+1
}
if t!=u{
heapSwap(t,u)
down(t)
}
}
func up(u int) {
if u/2 >0 && h[u/2]>h[u]{
heapSwap(u,u/2)
u>>=1
}
}
func heapSwap(a,b int) {
h[a],h[b] = h[b],h[a]
ph[hp[a]],ph[hp[b]] = ph[hp[b]],ph[hp[a]]
hp[a],hp[b] = hp[b],hp[a]
}
func add(a,b,c int) {
e[idx] = b
ne[idx] = hh[a]
w[idx] = c
hh[a] = idx
idx++
}
func readline(r *bufio.Reader) []int {
s, _ := r.ReadString('\n')
ss := strings.Fields(s)
res := make([]int, len(ss))
for i, v := range ss {
res[i], _ = strconv.Atoi(v)
}
return res
}
func dijkstra() int {
for i:=0;i<N;i++{
dist[i] = 0x3f3f3f3f
}
dist[1]=0
// 加堆
size++
ph[1] = size // 第一个加入的值在堆中的下标是1
h[size] = 0
hp[size] = 1 // 堆中下标为1的值是第1个加入的数
up(size)
for size>0{
// 取出堆中的最小值
distance := h[1]
ver :=hp[1]
// 堆中删除该点
heapSwap(1,size)
size--
down(1)
// 用取出的点逐一更新其他距离为正无穷的点
for i:=hh[ver];i!=-1;i=ne[i]{
j :=e[i] // i是节点的id,j是第j个插入的值
if dist[j]>distance+w[i]{
dist[j] = distance+w[i]
if ph[j]!=0{ //如果j不是第一个插入的,原来就已经在堆中,测试需要
// 修改的堆中的值
//h[j]=dist[j]
h[ph[j]]=dist[j]
up(ph[j])
down(ph[j])
}else {
// 新值加入到堆中
size++
h[size]=dist[j]
ph[j] = size
hp[size] = j
up(size)
}
}
}
}
if dist[n]==0x3f3f3f3f{
return -1
}
return dist[n]
}
func main() {
r := bufio.NewReader(os.Stdin)
fmt.Scanf("%d%d", &n, &m)
for i := 0; i < N; i++ {
hh[i] = -1
}
for m > 0 {
m--
in := readline(r)
a, b, z := in[0], in[1], in[2]
add(a, b, z)
}
fmt.Println(dijkstra())
}
时间复杂度
参考文献
作者:子非余安知余之美也
链接:https://www.acwing.com/solution/content/5631/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
C 代码,这个同学的c实现测试通过
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool found[N],st[N];
//这里就是手写堆的基本的三个函数的代码
int heap[N], hp[N], ph[N], sizee;
void heap_swap(int a, int b)
{
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(heap[a], heap[b]);
}
void down(int k)
{
int t = k;
if (k * 2 <= sizee && heap[t] > heap[k * 2]) t = k * 2;
if (k * 2 + 1 <= sizee && heap[t] > heap[k * 2 + 1]) t = k * 2 + 1;
if (k != t)
{
heap_swap(k, t);
down(t);
}
}
void up(int k)
{
while (k / 2 && heap[k] < heap[k / 2])
{
heap_swap(k, k / 2);
k >>= 1;
}
}
//下面是正文
//这里区分三个概念 节点的ID(即由idx形成的) (如果不理解说明数组实现单链表还没掌握)
// 节点(vertex) 即(题目样例中所给的每一行中前两个的那种数字)
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
sizee++;
ph[1] = sizee; //节点在堆中的下标
hp[sizee] = 1; //实现 用堆中的下标来识别这个是哪个vertex
heap[sizee] = 0;//存储距离 为了排序
up(sizee);
while (sizee)
{
int cur_dist = heap[1];
int cur_ver = hp[1];
heap_swap(1, sizee--);
down(1);
if (st[cur_ver]) continue;
st[cur_ver]=true;
for (int i = h[cur_ver]; i != -1; i = ne[i])
{
int j = e[i]; //i是节点ID j是vertex
if (dist[j] > cur_dist + w[i])
{
dist[j] = cur_dist + w[i];
if (ph[j] != 0)//修改之前已经在堆中的j节点
//记住 对于堆来说,他对 用来实现邻接表的idx 这个东西是没有概念的
//即这是一种对底层i的抽象 类似在cpu看来根本没有RAM和cahce之分
{
heap[ph[j]] = dist[j];
up(ph[j]);
down(ph[j]);
}
else//全新节点
{
sizee++;
ph[j] = sizee;
hp[sizee] = j;
heap[sizee] = dist[j];
up(sizee);
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
cout << dijkstra();
}