题目描述
blablabla
思路
利用优先队列(小根堆) 来实现优化
关于求最短路径,可以先看看
https://www.acwing.com/solution/content/34124/
朴素的:
① dist[1] = 0, dist[i] = -INF
② for i in 1…n:
t <- 不在s中 要遍历每一个点 n次
s <- t
用t更新其他点 更改每一个点 n次
总的时间复杂度O(n^2)
堆优化的:
① dist[1] = 0, dist[i] = -INF
② for i in 1…n: => while(堆不为空)
t <- 不在s中 要遍历每一个点 n次 => 因为遍历的目的是为了找到最小距离,所以需要利用小根堆堆来实现O(1),取堆顶,总的为n
s <- t
用t更新其他点 更改每一个点 n次 => 更改每一个点需要比较n次,有了栈,只需要将遍历边m(总的当前点的边),总的时间O(mlogn),其中logn是比较次数。
总的时间复杂度O(mlogn)
java
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static int n, m;
static int N = 150010, V = 0x3f3f3f3f;
static int[] h = new int[N], ne = new int[N], e = new int[N], w = new int[N];
static int idx;
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {return o1[1] - o2[1];});
private static void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
private static int dijkstra() {
Arrays.fill(dist, V);
dist[1] = 0;
queue.offer(new int[]{1, 0}); // 点 距离
while(!queue.isEmpty()) {
int[] t = queue.poll();
int ver = t[0], distance = t[1];
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
queue.offer(new int[] {j, dist[j]});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);
}
System.out.println(dijkstra());
}
}
c ++
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // 距离 -> 节点
while(heap.size()){
auto t = heap.top();
heap.pop();
//其实本质是贪心,每次更新一个最短路径
int ver = t.second, distance = t.first;
//因为会出现上一次最短路径更新了a -> b -> c 依据最短路径b找到了c,说明当前最短a->b已经是最短的了
//如果有a -> d - > b 显然a更新了b, a->d->b,对b不需要更新
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > distance + w[i]){
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
//不需要考虑自环和重边
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}
5555没有py
写的很好