Dijkstra + 两个小递推

#include <iostream>
#include <queue>
#include <cstring>

#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)

using namespace std;
const int N = 550;
const int M = 650;
const int oo = 0x7f7f7f7f;

int head[N], edge_cnt;

struct Edge {
  int to, w, nxt;
} edges[M << 1];

inline void addEdge(int u, int v, int w) {
  edges[++edge_cnt] = {v, w, head[u]};
  head[u] = edge_cnt;
}

int n, m, c1, c2, teams[N];

inline void print_graph(void) {
  f(u, 0, n) {
    printf("vertex %ld: [ ", u);
    for (int e = head[u]; e; e = edges[e].nxt)
      printf("(%d, %d) ", edges[e].to, edges[e].w);
    puts("]");
  }
}

inline void dijkstra(void) {
  int dists[N], seen[N] = {0}, cnts[N] = {0}, cnts2[N] = {0};
  memset(dists, oo, sizeof dists);
  dists[c1] = 0, cnts[c1] = 1, cnts2[c1] = teams[c1];

  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  pq.emplace(0, c1);

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

    if (curr == c2) break; // 一个剪枝

    for (int e = head[curr], nxt, w; e; e = edges[e].nxt) {
      nxt = edges[e].to, w = edges[e].w;
      if (dist + w < dists[nxt]) {
        dists[nxt] = dist + w;
        cnts[nxt] = cnts[curr];
        cnts2[nxt] = teams[nxt] + cnts2[curr];
        pq.emplace(dists[nxt], nxt);
      } else if (dist + w == dists[nxt]) {
        cnts[nxt] += cnts[curr];
        cnts2[nxt] = max(cnts2[nxt], cnts2[curr] + teams[nxt]);
      }
    }
  }

  printf("%d %d\n", cnts[c2], cnts2[c2]);
} 

signed main(int argc, char const *argv[]) {
  scanf("%d%d%d%d", &n, &m, &c1, &c2);
  f(i, 0, n) scanf("%d", teams + i);

  for (int u, v, w; m--;) {
    scanf("%d%d%d", &u, &v, &w);
    addEdge(u, v, w);
    addEdge(v, u, w);
  }

  // print_graph();
  dijkstra();
  return ~~(0 ^ 0);
}

dijkstra 扩展题

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;

using P = pair<int, int>;
int n, m, s, t, u, v, w;

void dijkstra(vector<vector<pair<int, int>>>& g, 
              vector<int>& dist,
              vector<int>& paths,
              vector<int>& teams,
              vector<int>& nums) {

  priority_queue<P, vector<P>, greater<P>> pq;
  pq.emplace(0, s);

  vector<int> seen(n);
  dist[s] = 0;
  nums[s] = teams[s];
  paths[s] = 1;

  while (not pq.empty()) {
    const auto [d, cur] = pq.top(); pq.pop();

    if (seen[cur]) continue;
    seen[cur] = 1;

    for (const auto& [nei, w] : g[cur]) {
      if (seen[nei]) continue;
      if (d + w < dist[nei]) {
        nums[nei] = nums[cur] + teams[nei];
        paths[nei] = paths[cur];
        dist[nei] = d + w;
        pq.emplace(d + w, nei);
      } else if (d + w == dist[nei]) {
        if (nums[cur] + teams[nei] > nums[nei])
           nums[nei] = teams[nei] + nums[cur];
        paths[nei] += paths[cur];
      }
    }
  }
}

int main(void) {
  scanf("%d %d %d %d", &n, &m, &s, &t);
  vector<int> teams(n);
  for (int i = 0; i < n; ++i) cin >> teams[i];

  vector<vector<pair<int, int>>> g(n);
  vector<int> dist(n, INF);
  vector<int> paths(n), nums(n); // 变量名不知道怎么起系列

  while (m--) {
    scanf("%d %d %d", &u, &v, &w);
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }

  dijkstra(g, dist, paths, teams, nums);
  return printf("%d %d\n", paths[t], nums[t]), 0;
}