xiaobu_dean @ 2023-11-01 12:59:48
// 堆优化的dijkstra算法
// 通过使用优先对列优化了朴素dijkstra算法中找离当前源点最近的点
// q.push_back({w,v}),w为v到源点的距离
// 将权值放在第一位是因为pair中会优先对第一个元素排序
// 1.邻接表存储
/*#include <bits/stdc++.h>
#define inf INT_MAX;
using namespace std;
using ll = long long ;
const int N = 1e5 + 50;
int n,m,s;
struct edge {int v,w;};
vector<edge> e[N];
int d[N];
bool vis[N];
priority_queue<pair<int,int> > q;
void dijkstra(int s) {
for (int i = 1;i <= n; i++) d[i] = inf;
d[s] = 0;
q.push({0,s});
while (q.size()) {
auto t = q.top(); q.pop();
int u = t.second;
if (vis[u]) continue;
vis[u] = true;
for (auto c:e[u]) {
int v = c.v; int w = c.w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w; // 松弛操作
q.push({-d[v],v});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> s;
for (int i = 1;i <= m; i++) {
int u,v,w; cin >> u >> v >> w;
e[u].push_back({v,w});
}
dijkstra(s);
for (int i = 1;i <= n; i++) cout << d[i] << " ";
return 0;
}*/
// 2.链式前向星存储
#include <bits/stdc++.h>
#define inf INT_MAX;
using namespace std;
using ll = long long ;
const int N = 1e5 + 50 ;
int n,m,s;
struct edge {
int to,ne,w;
}edge[N];
int head[N],cnt;
void add(int u,int v,int w) {
cnt++;
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].ne = head[u];
head[u] = cnt;
}
int d[N];
bool vis[N];
priority_queue<pair<int,int> > q;
void dijkstra(int s) {
for (int i = 1;i <= n; i++) d[i] = inf;
d[s] = 0;
q.push({0,s});
while (q.size()) {
auto t = q.top();q.pop();
int u = t.second;
if (vis[u]) continue;
vis[u] = true;
for (int i = head[u];i>0;i = edge[i].ne) {
int v = edge[i].to;
int w = edge[i].w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push({-d[v],v}); // 权值是-d[v],不是w也不是d[v]
}
}
}
}
// 以上为链式前向星模版
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> s;
for (int i = 1;i <= m; i++) {
int u,v,w; cin >> u >> v >> w;
add(u,v,w);
}
dijkstra(s);
for (int i = 1;i <= n; i++) cout << d[i] << " ";
return 0;
}
上面注释掉的是我用vector模拟邻接表存储的,已经AC了,然后想着用链式前向星写一下,结果RE了四个点
by Aesyl @ 2023-11-01 13:12:45
邻接表大小为点数,前向星大小为边数(双向算两条边)
by Aesyl @ 2023-11-01 13:13:25
本题边数为2x10^5
by xiaobu_dean @ 2023-11-01 18:01:25
@Daffod_Tequila orz