1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void dijkstra(int s) {
  dis[s] = 0;
  vis[s] = 1;
  for (int i = 2; i <= n; i++) dis[i] = g[s][i];
  for (int i = 1; i <= n; i++) {
    int minDis = 0x3f3f3f3f;
    for (int j = 2; j <= n; j++)
      if (!vis[j] && minDis > dis[j]) {
        minDis = dis[j];
        u = j;
      }
    vis[u] = 1;
    for (int v = 1; v <= n; v++)
      if (!vis[v] && dis[n] + g[u][v] < dis[v]) dis[v] = dis[u] + g[u][v];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void dijkstra(int s) {
    q.push({0, s});
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    while (!q.empty()) {
        pair<ll, int> p = q.top();
        q.pop();
        int u = p.second;
        ll ww = p.first;

        if (dis[u] < ww) continue;

        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (dis[v] > dis[u] + w[u][i]) {
                dis[v] = dis[u] + w[u][i];
                q.push({dis[v], v});
            }
        }
    }
}