复习版

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define not !
#define and &&
#define or ||

#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)

#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 0 : 10); }

typedef long long int ll;
#define r() fast_read()

bool is_digit(const char c) {
  return c >= 48 and c <= 57;
}

ll fast_read(void) {
  ll n = 0, sign = 1;
  char c = getchar();
  while (not is_digit(c)) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (is_digit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

#define N 520
#define oo 0x7f7f7f7f

typedef struct {
  int dist;
  int cost;
} City;

int n, m, s, d;
City adj[N][N];

void print_adj(void) {
  rep(u, 0, n) {
    rep(v, 0, n) printf("(%10d, %10d)\t", adj[u][v].dist, adj[u][v].cost);
    putchar(10);
  }
}

void show_path(int* P, int x) {
  if (x == -1) return;
  show_path(P, *(P + x));
  printf("%d ", x);
}

// 朴素版的dijkstra
void dijkstra(void) {
  bool S[N] = {0};
  int P[N], C[N] = {0}, D[N];
  // 算法初始化部分
  rep(i, 0, n) {
    D[i] = oo, P[i] = -1;
    if (adj[s][i].dist != oo)
      D[i] = adj[s][i].dist, P[i] = s, C[i] = adj[s][i].cost;
  }
  S[s] = 1, D[s] = 0;

  rep(i, 0, n - 1) { // 算法共执行n - 1循环
    // 找最小
    int min_d = oo, t = s;
    rep(j, 0, n) {
      if (not S[j] and D[j] < min_d) {
        min_d = D[j];
        t = j;
      }
    }

    if (t == s) break;
    S[t] = 1; // 加入S集合

    // 松驰
    rep(j, 0, n) {
      if (S[j]) continue;
      if (D[t] + adj[t][j].dist < D[j]) {
        D[j] = D[t] + adj[t][j].dist;
        C[j] = C[t] + adj[t][j].cost;
        P[j] = t;
      } else if (D[t] + adj[t][j].dist == D[j]) {
        if (C[t] + adj[t][j].cost < C[j]) {
          C[j] = C[t] + adj[t][j].cost;
          P[j] = t;
        }
      }
    }
  }

  show_path(P, d);
  printf("%d %d\n", D[d], C[d]);
}

signed main(int argc, char const *argv[]) {
  // freopen("test.in", "r", stdin);

  n = r(), m = r(), s = r(), d = r();
  memset(adj, oo, sizeof adj);
  for (int u, v, dist, cost; m--;) {
    u = r(), v = r(), dist = r(), cost = r();
    adj[u][v] = adj[v][u] = (City) {dist, cost};
  }

  // print_adj();
  dijkstra();
  // fclose(stdin);
  return ~~(0 ^ 0);
}

堆优化版 Dijkstra Algorithm 拓展题！

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <algorithm>

using namespace std;
using P = pair<int, int>;
const int INF = 0x3f3f3f3f;

int N, M, S, D;
int a, b, c, d;

void dijkstra(vector<vector<tuple<int, int, int>>>& g,
              vector<int>& dists,
              vector<int>& costs,
              vector<int>& parents) {

  priority_queue<P, vector<P>, greater<P>> pq;
  pq.emplace(0, S);
  vector<int> seen(N);
  dists[S] = 0;
  parents[S] = -1;

  while (not pq.empty()) {
    const auto [d, u] = pq.top(); pq.pop();
    if (seen[u]) continue;
    seen[u] = 1;

    for (const auto& [v, dist, cost] : g[u]) {
      if (seen[v]) continue;
      if (d + dist < dists[v]) {
        costs[v]   = costs[u] + cost;
        parents[v] = u;
        dists[v]   = d + dist;
        pq.emplace(d + dist, v);
      } else if (d + dist == dists[v]) {
        if (costs[u] + cost < costs[v]) {
          costs[v] = costs[u] + cost;
          parents[v] = u;
        }
      }
    }
  }
}

// debug helper function
void printGraph(vector<vector<tuple<int, int, int>>>& g) {
  for (int u = 0; u < N; ++u) {
    printf("%d: [", u);
    for (const auto& t : g[u])
      printf("(%d, %d, %d) ", get<0>(t), get<1>(t), get<2>(t));
    printf("]\n");
  }
}

int main(void) {
  cin >> N >> M >> S >> D;

  vector<vector<tuple<int, int, int>>> g(N);
  vector<int> dists(N, INF), parents(N), costs(N);

  while (M--) {
   cin >> a >> b >> c >> d;
   g[a].emplace_back(b, c, d);
   g[b].emplace_back(a, c, d);
  }

  // printGraph(g);
  dijkstra(g, dists, costs, parents);
  // for (int i = 0; i < N; ++i)
  //   printf("%d: [dist = %-2d cost = %-2d parent = %-2d]\n", i, dists[i], costs[i], parents[i]);

  int p = D;
  vector<int> paths;
  while (p != -1) {
    paths.emplace_back(p);
    p = parents[p];
  }

  std::reverse(begin(paths), end(paths));
  for (const auto& x : paths) printf("%d ", x);
  return printf("%d %d\n", dists[D], costs[D]), 0;
}