C++，给定一张n个点m条边的有向图，统计有多少点满足：从图上任意点出发，都可以沿图上的有向边到达这个点

以下是使用动态规划算法求解的 C++ 代码： ```cpp #include <iostream> #include <cstring> using namespace std; const int MAXN = 20; const int MAXS = 1 << MAXN; const int MOD = 998244353; int n; int g[MAXN][MAXN]; int dp[MAXS]; bool vis[MAXS]; int dfs(int s) { if (vis[s]) { return dp[s]; } vis[s] = true; if (s == (1 << n) - 1) { dp[s] = 1; return dp[s]; } int u; for (u = 0; u < n; u++) { if ((s & (1 << u)) == 0) { break; } } int &ans = dp[s]; for (int v = u + 1; v < n; v++) { if ((s & (1 << v)) == 0 && g[u][v]) { ans = (ans + dfs(s | (1 << u) | (1 << v))) % MOD; } } return ans; } int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> g[i][j]; } } memset(vis, false, sizeof(vis)); cout << dfs(0) << endl; return 0; } ``` 其中，`g[i][j]` 表示从顶点 `i` 到顶点 `j` 是否存在一条有向边。`dp[s]` 表示状态为 `s` 的有标号单图数。`vis[s]` 表示状态 `s` 是否已经被访问过。在 `dfs` 函数中，通过枚举两个未被访问的顶点 `u` 和 `v`，如果从 `u` 到 `v` 存在一条有向边，则递归计算状态 `s | (1 << u) | (1 << v)` 的有标号单图数，并累加到答案中。最后返回状态为 0 的有标号单图数即可。

您提到的内容涉及的是一个典型的 **单源最短路径** 问题，并附有一个具体的题目背景以及相关的输入输出格式说明。以下是对此内容的具体解析： --- ### 单源最短路径 (SSSP) 概述 #### 定义 单源最短路径问题是图论中的经典问题之一，目标是从某个起点出发，找到到达所有其他节点的最短距离。如果图中边权重均为非负，则可以使用经典的 Dijkstra 算法解决该问题。 #### 输入分析 根据您的描述： - 图中有 `n` 个顶点和 `m` 条有向边； - 边 `(ui, vi)` 的权重为 `wi`； - 起始点固定为 `s = 1`； 我们需要通过某种算法（如Dijkstra 或 SPFA），计算出从起始点到每一个点的距离。 --- ### 示例解释 - 样例数据分析 对于样例数据： ``` 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 ``` 我们可以构建如下加权有向图： - 节点编号：1、2、3、4； - 边及权重信息如下表所示： | u | v | w | |---|---|---| | 1 | 2 | 2 | | 2 | 3 | 2 | | 2 | 4 | 1 | | 1 | 3 | 5 | | 3 | 4 | 3 | | 1 | 4 | 4 | 运行 Dijkstra 后的结果是 `[0, 2, 4, 3]`，即分别为从起点 1 到各节点的最小代价。 --- ### 解决方案步骤 我们可以通过优先队列优化版本的 **Dijkstra 算法** 实现此功能，其时间复杂度大约为 \(O(m \log n)\)，适用于大规模稀疏图。下面是基于 C++ 的伪代码实现框架： ```cpp #include <bits/stdc++.h> using namespace std; const long long INF = LLONG_MAX; // 设置无穷大 int main() { int n, m, s; cin >> n >> m >> s; vector<vector<pair<int, int>>> graph(n + 1); // 构建邻接表存储图 for(int i = 0;i<m;i++) { // 初始化边 int ui, vi, wi; cin>>ui>>vi>>wi; graph[ui].emplace_back(vi, wi); } priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> pq; // 小根堆用于选取当前最优路径 vector<long long> dist(n+1,INF); dist[s]=0; pq.emplace(0LL,s); while(!pq.empty()) { auto [curDist,node] = pq.top(); pq.pop(); if(curDist >dist[node]) continue;// 剪枝 for(auto &[nextNode,nextCost]:graph[node]){ if(dist[nextNode]>dist[node]+ nextCost){ dist[nextNode] = dist[node] + nextCost; pq.emplace(dist[nextNode],nextNode); } } } for(int node=1;node<=n;node++) cout<<dist[node]<<" "; // 输出结果至文件或屏幕 } ``` 上述程序实现了以下关键操作： 1. 使用了优先队列加速访问最近未处理结点的操作。 2. 动态更新每个点的最佳可达成本并加入待探索集合。 --- ###