B3976的最简单的题解

szm111213 · 2024-08-05 19:44:00 · 个人记录

题目做法

这题太简单了一看就要用图论里的Dijkstra算法做

我的思路

构建一个结构体，存下节点的数量和邻接表，然后就是Dijkstra算法啦，话不多说，直接放上简简单单77行代码

参考代码

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

using namespace std;

// 图的结构体
struct Graph {
    int n; // 节点数量
    vector<vector<pair<int, int>>> adj; // 邻接表

    Graph(int n) : n(n), adj(n) {}

    void addEdge(int u, int v, int w) {
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
};

// Dijkstra算法
vector<int> dijkstra(const Graph& graph, int start) {
    vector<int> dist(graph.n, INT_MAX);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, start);

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (const auto& edge : graph.adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }

    return dist;
}

int main() {
    string s;
    cin >> s;

    int n = s.length();
    Graph graph(n);

    // 构建图
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (isalpha(s[i]) && isalpha(s[j])) {
                graph.addEdge(i, j, abs(i - j));
            }
        }
    }

    // 使用Dijkstra算法找到最短路径
    vector<int> dist = dijkstra(graph, 0);

    // 输出结果
    for (int i = 0; i < n; ++i) {
        if (isalpha(s[i])) {
            cout << s[i];
        }
    }
    cout << endl;

    return 0;
}