• 题意：
  • 给出一个无向图和每条边的权值，给出一个点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;
}