朴素版与堆优化版时间复杂度比较
朴素版时间复杂度$O(n^2)$
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j; // O(n) * O(n) -> O(n^2)
}
st[t] = true; // O(n) * O(1) -> O(n)
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]); //O(n) * O(n) -> O(n^2)
}
}
堆优化版时间复杂度$O(mlog(n))$
//遍历大部分的边
while (heap.size()) {
auto t = heap.top(); //O(m) * O(1) -> O(m)
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver])continue;
st[ver] = true; //O(m) * O(1) -> O(m)
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});
// 堆的插入操作时间复杂度是 O(log(n))
// O(m) * O(log(n)) -> O(mlog(n))
}
}
}
课堂截图
区别
稠密图使用邻接矩阵存储
稀疏图使用邻接表存储
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> PII; //<离起点的距离, 节点编号>
const int N = 150010;
int h[N], e[N], ne[N], idx, w[N];
int dist[N];
bool st[N];
int n, m;
//在a节点之后插入一个b节点,权重为c
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);
// 1号节点距离为0
dist[1] = 0;
// 建立一个小根堆
priority_queue<PII, vector<PII>, greater<PII>> heap;
// 1号节点插入堆
heap.push({0, 1});
while (heap.size()) {
// 取出堆顶顶点
auto t = heap.top();
// 并删除
heap.pop();
// 取出节点编号和节点距离
int ver = t.second, distance = t.first;
// 如果节点被访问过,则跳过
if (st[ver])continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
// 取出节点编号
int j = e[i];
// dist[j] 大于从t过来的距离
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() {
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}
(๑′ᴗ‵๑)I Lᵒᵛᵉᵧₒᵤ❤
不知道为啥有一组数据过不了,但是提交是ac的
能ac就可以了,可以看看这个。常见问题
嘿嘿,好的,谢谢你~~。
xd,你这个可以AC吗,我去试了一下TLE了
据说改了数据
好吧:(
可以AC了
怎么判断是稀疏图还是稠密图啊?
比较 849 和 850, 二者数据量是不同的,849存储空间使用太大;
稠密图边与点差几个数量级,稀疏图边和点在一个数量级上,相差不大
谢谢老哥
n=m稀疏图,m^2稠密图
n是点,m是边
判断主要是看边的数量
m和n^2是一个级别,是稠密图
m和n一个级别,是稀疏图
楼主楼主 请问这道题是怎么看出是稀疏图的呀 题目中也没给出m<n呀 谢谢楼主
n和m 一个数量级时是稀疏图,n ~ m^2 时是稠密图
谢谢xd
n是点,m是边
m和n^2是一个级别,才是稠密图