disjkstra算法

图的两种表示方式

1. 邻接矩阵

优点：方便查找，方便操作
缺点：需要空间过大

#define MAX_N 1000
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
#define lfr(i, x, y) for (int i = x; i >= y; --i)
int G[MAX_N];
signed main(){
  cin >> n;
  ufr(i,1,n){
    int from,to,cost;
    cin >> from >> to >> cost;
    G[from][to]=cost;
  }
  return 0;
}

2. 邻接链表

优点：存储空间小
缺点：查找指定边时间复杂度高

#define MAX_N 1000
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
#define lfr(i, x, y) for (int i = x; i >= y; --i)
// 使用priority_queque时默认为最小堆
struct vertex {
  int from, to, cost;
  vertex(int from_, int to_, int cost_) : from(from_), to(to_), cost(cost_) {}
  vertex(int to_, int cost_) : to(to_), cost(cost_) {}
  vertex(int from_, int to_, bool token) : from(from_), to(to_) {}
  bool operator<(const vertex& v) const { return this->cost > v.cost; }
  bool operator==(const vertex& v) const {
    return this->from == v.from && this->to == v.to;
  }
};
int n,m;
ll dis[MAX_N];
vector<vertex> G[MAX_N];
signed main() {
  n = f.r(), m = f.r();
  ufr(i, 1, m) {
    from = f.r(), to = f.r(), cost = f.r();
    G[from].emplace_back(to, cost);
  }
  return 0;
}

算法使用

创建一个静态数组来存储源节点到其余结点的权值ll dis[MAX_N];
首先将源结点到其本身的权值设置为0，其余设为正无穷，然后将其放入一个小根堆构成的优先队列中

  fill(goto(dis, n), 2147483647);
  dis[s] = 0;
  priority_queue<vertex> que;
  que.emplace(s, dis[s]);

然后开始循环当\(que\)为空时结束循环，每次循环从\(que\)中取出距离到达源点距离最小的权值结点，首先进行判断，因为后面的操作都是增加操作，所有如果当前到达源点的权值小于本点，直接\(continue\)。然后遍历该结点，依次放入比现在到达源点的权值小的结点和其权值

  while (!que.empty()) {
    vertex v = que.top();
    que.pop();
    if (dis[v.to] < v.cost) continue;
    for (const vertex& ver : G[v.to]) {
      if (dis[ver.to] > v.cost + ver.cost) {
        dis[ver.to] = v.cost + ver.cost;
        que.emplace(ver.to, dis[ver.to]);
      }
    }
  }

最后遍历输出一下就行了

模板题目

click

#include <bits/stdc++.h>
#define _i i << 1
#define __i i << 1 | 1
#define cl tree[i].l
#define cr tree[i].r
#define mod(x) ((x) % MOD)
#define lowbit(x) (x & -x)
#define g1(x) get<0>(x)
#define g2(x) get<1>(x)
#define g3(x) get<2>(x)
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
#define lfr(i, x, y) for (int i = x; i >= y; --i)
#define all(x) x.begin(), x.end()
#define goto(x, y) x + 1, x + y + 1
#define mm(x, y) memset(x, y, sizeof(x))
using namespace std;
using ld = long double;
using ll = long long;
using pp = pair<int, int>;

namespace Solution {
class fastio {
 public:
  template <class T = int>
  inline T r() noexcept {
    T x = 0, w = 1;
    char ch = 0;
    for (; !isdigit(ch); ch = getchar())
      if (ch == '-') w = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch - '0');
    return x * w;
  }
  inline string rs() noexcept {
    string res;
    char ch = 0;
    for (ch = getchar(); ch == '\0' || ch == '\n' || ch == '\r'; ch = getchar())
      ;
    for (; ch != '\n' && ch != '\r'; ch = getchar()) res.append(1, ch);
    return res;
  }
  inline char rc() noexcept {
    char ch = getchar();
    for (; ch == '\0' || ch == '\n' || ch == '\r' || ch == ' '; ch = getchar())
      ;
    return ch;
  }

  template <class T = int>
  inline fastio& pt(T x) noexcept {
    static char sta[128];
    int top = 0;
    if (x < 0) x = -x, putchar('-');
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48);
    return *this;
  }

  inline fastio& pts(const string s) noexcept {
    for (int i = 0; s[i] != '\0'; ++i) putchar(s[i]);
    return *this;
  }
  inline fastio& ptc(const char c) noexcept {
    putchar(c);
    return *this;
  }
  inline fastio& ln() noexcept {
    putchar('\n');
    return *this;
  }
} f;
// 使用priority_queque时默认为最小堆
struct vertex {
  int from, to, cost;
  vertex(int from_, int to_, int cost_) : from(from_), to(to_), cost(cost_) {}
  vertex(int to_, int cost_) : to(to_), cost(cost_) {}
  vertex(int from_, int to_, bool token) : from(from_), to(to_) {}
  bool operator<(const vertex& v) const { return this->cost > v.cost; }
  bool operator==(const vertex& v) const {
    return this->from == v.from && this->to == v.to;
  }
};

struct pp_hash {
  template <class T1, class T2>
  std::size_t operator()(const std::pair<T1, T2>& p) const {
    auto h1 = std::hash<T1>{}(g1(p));
    auto h2 = std::hash<T2>{}(g2(p));
    return h1 ^ h2;
  }
};
// less --> return __x < __y; || greater --> return __x > __y;
#define MAX_N 1001000
static constexpr ll MOD = 1e9 + 7;
static constexpr ll eps = -1e9;
static constexpr ll inf = 0x7fffffff;
int n, m, s, to, from, cost;
ll dis[MAX_N];
vector<vertex> G[MAX_N];
void solve() {
  priority_queue<vertex> que;
  que.emplace(s, dis[s]);
  while (!que.empty()) {
    vertex v = que.top();
    que.pop();
    if (dis[v.to] < v.cost) continue;
    for (const vertex& ver : G[v.to]) {
      if (dis[ver.to] > v.cost + ver.cost) {
        dis[ver.to] = v.cost + ver.cost;
        que.emplace(ver.to, dis[ver.to]);
      }
    }
  }
  ufr(i, 1, n) f.pt(dis[i]).ptc(' ');
}
}  // namespace Solution

signed main() {
  using namespace Solution;
  unordered_map<pp, int, pp_hash> mp;
  n = f.r(), m = f.r(), s = f.r();
  ufr(i, 1, m) {
    from = f.r(), to = f.r(), cost = f.r();
    G[from].emplace_back(to, cost);
  }
  fill(goto(dis, n), 2147483647);
  dis[s] = 0;
  solve();
  return 0;
}