Dijkstra 算法求解图中路径满足需求点距离限制

本题是求解在给定的图中，从每个起点出发，是否存在一条路径满足所有需求点之间的距离和不超过 'D'。因此，我们可以考虑对于每个起点 'i'，使用 Dijkstra 算法求出其到其他所有点的最短路径，并判断是否存在一条路径满足所有需求点的限制。

首先，读入输入数据。使用邻接表存储图的结构，然后读入需求点的位置。

接下来，对于每个起点 'i'，我们使用 Dijkstra 算法求出其到其他所有点的最短路径。具体实现中，我们使用一个小根堆维护当前需要更新的点，每次取出距离 'i' 最近的点 'u'，然后遍历 'u' 的所有邻居 'v'，如果从 'i' 到 'v' 的距离可以通过从 'i' 到 'u' 再到 'v' 的距离更新，则更新 'dist[v]' 的值，并将 'v' 插入堆中。

最后，对于每个需求点 '(s, t)'，判断 'dist[s]' 和 'dist[t]' 是否都不为 'INF'，并且 'dist[s]+dist[t]<=D'。如果存在一条路径满足需求，则令答案增加 '1'。

最终，输出答案即可。

#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

void dijkstra(int s, const vector<vector<pair<int, int>>>& adj, vector<int>& dist) {
    int n = adj.size();
    dist.assign(n, INF);
    dist[s] = 0;

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

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (dist[u] < d) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
}

int main() {
    int N, M, T, P, D;
    cin >> N >> M >> T >> P >> D;

    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    vector<pair<int, int>> demands(T);
    for (int i = 0; i < T; i++) {
        int s, t;
        cin >> s >> t;
        demands[i] = {s, t};
    }

    int ans = 0;
    for (int i = 0; i < P; i++) {
        vector<int> dist(N);
        dijkstra(i, adj, dist);
        for (auto [s, t] : demands) {
            if (dist[s] != INF && dist[t] != INF && dist[s] + dist[t] <= D) {
                ans++;
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}