dij算法与小根堆

dij即利用一个小根堆

每次取出队头元素，利用队头元素对其他点进行松弛

每当一个点出队，说明他已经是被最小元素松弛过，那么不可能有更优解，那么便打上标记

松弛时注意目标点是否已经出队，如果出队说明不能再被松弛

注意：dij只能用于没有负边的图内

复杂度为O（mlogm)

struct node
{
  int x,val;
  bool operator<(const node &x)const
  {
      return val>x.val;
  }
};


void dij(int s)
{
  priority_queue<node> q;
  for (int i = 1; i <= n; i++) dis[i] = 1e9;
  memset(vis, 0, sizeof(vis));
  dis[s] = 0;
  q.push(node{s,0});
  while (!q.empty())
  {
    int u = q.top().x;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; i; i = nxt[i])
    {
      int v = to[i];
      if (dis[v] > dis[u] + val[i])
      {
        dis[v] = dis[u] + val[i];
        if (!vis[v]) q.push(node{v, dis[v]});
      }
    }
  }
  return;