spfa单源最短路
- 题意：
- 给出一个无向图和每条边的权值，给出一个点s，问你s点到任意点的最短距离，就是dij，但是dij要开二维数组，如果节点的个数大于等于1e5，dij绝对爆内存。
- 题解：
- spfa算法。
- 代码：
#include <bits/stdc++.h> using namespace std; #define ll long long const ll inf = 1e18; const int maxx = 1e5+10; struct node{ int to; ll w; friend bool operator <(node p1,node p2){ return p1.w > p2.w; } }; int n,m; vector<node> v[maxx]; priority_queue<node> q; ll dis[maxx],a[maxx]; void spfa(int s) { fill(dis+1,dis+1+n,inf); dis[s] = 0; while(!q.empty()) q.pop(); q.push(node{s,0}); while(!q.empty()) { node x = q.top();q.pop(); int k = x.to; int w = x.w; if(w > dis[k]) continue; for(int i=0;i<v[k].size();i++){ if(dis[v[k][i].to] > w + v[k][i].w){ dis[v[k][i].to] = w + v[k][i].w; q.push(node{v[k][i].to,dis[v[k][i].to]}); } } } } int main() { int x,y,l; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d %d %d",&x,&y,&l); v[x].push_back({y,l}); v[y].push_back({x,l}); } scanf("%d",&x); spfa(x); for(int i=1;i<=n;i++) { printf("%lld ",dis[i]); } return 0; }
