题解 | # 2026年4月25日题解 #
单个点不算
求若干个起点到若干个终点的总路径数
DFS超时了，其实是一个个路径权值叠加的关系，用拓扑排序解决：只有当前节点前面的路径都更新完了我再去更新下一个节点
总代码：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
const int N = 100000 + 100;
int n, m;
vector<int> adj[N];
int deg[N], w[N];
void solve(){
cin >> n >> m;
for(int i = 1; i <= m; i ++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
deg[v] ++;
}
queue<int> q;
for(int i = 1; i <= n; i ++){
if(!deg[i] && adj[i].size()){
q.push(i);
w[i] = 1;
}
}
while(q.size()){
int u = q.front();
q.pop();
for(int v : adj[u]){
w[v] += w[u];
if(-- deg[v] == 0) q.push(v);
}
}
int ans = 0;
for(int i = 1; i <= n; i ++){
if(!adj[i].size()) ans += w[i];
}
cout << ans << endl;
return ;
}
signed main(){
HelloWorld;
int tt = 1;
while(tt --) solve();
return 0;
}
简单说就是给定n个点，m条边，以及k个点，然后求这k个点里面任意两点之间的最短距离的最小值
一开始给我整蒙了，不会呀，以为是求任意两点之间的最短距离，以为是floyd算法，但时间复杂度为O(n^3)，肯定爆了，但是又有区别，不需要求任意两点之间的最短路径，只需要求所有路径中的最短值
只好看题解了：多源dijkstra+思维
首先将这k个点全部加入到优先队列中，然后需要记录每个节点的最短路径以及这个节点是从哪个节点走过来的，用from[i]表示吧
那么例如这k个点里面有两个点a和b，存在这样的一条路径a -> ....-> u -> v -> ....-> b，那么a和b之间的最短路径就等于dist[u]+dist[v]+w(u,v)，但是前提是u和v之间存在一条边并且from[u]=a,from[v] = b
总代码：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
const int N = 100000 + 100;
int n, m, k;
vector<pair<int, int> > adj[N];
int a[N], dist[N], vis[N], from[N];
struct Node{
int u, v, w;
};
struct cmp{
bool operator() (const pair<int, int> &a, const pair<int, int> &b) const{
return a.second > b.second;
}
};
void solve(){
cin >> n >> m >> k;
for(int i = 1; i <= k; i ++) cin >> a[i];
vector<Node> b(m + 10);
for(int i = 1; i <= m; i ++){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
b[i] = {u, v, w};
}
memset(dist, 0x3f3f3f3f, sizeof(dist));
priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> q;
for(int i = 1; i <= k; i ++){
dist[a[i]] = 0;
q.push({a[i], 0});
from[a[i]] = a[i];
}
while(q.size()){
int u = q.top().first;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto [v, w] : adj[u]){
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
from[v] = from[u];
q.push({v, dist[v]});
}
}
}
int ans = 1000000000000000000;
for(int i = 1; i <= m; i ++){
int u = b[i].u, v = b[i].v, w = b[i].w;
if(from[u] && from[v] && from[u] != from[v]){
ans = min(ans, dist[u] + dist[v] + w);
}
}
cout << ans << endl;
return ;
}
signed main(){
HelloWorld;
int tt = 1;
while(tt --) solve();
return 0;
}
忘了怎么写Floyd算法了，写一遍温故一下：
总代码：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
const int N = 100 + 10;
int n, m, q;
int dist[N][N];
void solve(){
memset(dist, 0x3f3f3f3f, sizeof(dist));
cin >> n >> m >> q;
for(int i = 1; i <= n; i ++) dist[i][i] = 0;
for(int i = 1; i <= m; i ++){
int u, v, w; cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
}
for(int k = 1; k <= n; k ++){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
while(q --){
int u, v; cin >> u >> v;
cout << dist[u][v] << endl;
}
return ;
}
signed main(){
HelloWorld;
int tt = 1;
while(tt --) solve();
return 0;
}
查看16道真题和解析