题解：P16472 [GKS 2013 #A] Spaceship Defence

· · 题解

题目思路

Dijkstra，只不过建图有点复杂，每个节点对应了一个颜色，相同颜色的节点距离为 0。

看到第一眼，想到两种方案：

显然，第一种会炸空间，考虑第二种。

用一个哈希表 p 存储颜色，输入 s_{i} 代表第 i 个节点的颜色 s_{i}，记录 s_{i} 的辅助节点，辅助节点的编号从 n + 1 开始，用 cnt 存储，如果第一次遇到该颜色，那么设置这个颜色的辅助节点为 cnt，并将 cnt + 1。

存完后，开始建邻接表，分两部分，第一部分，将相同颜色于辅助节点连接，第 i 个节点对应的颜色即为 p_{s_{i}}，第二部分，正常建 m 条边。

接着 Dijkstra 即可。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Node {
    int v, w;
};

struct node {
    int u, d;
    bool operator < (const node &a) const {
        return d > a.d;
    }
};

inline void solve(int Case) {
    cout << "Case #" << Case << ":" << '\n';
    int n, m, T;
    string s[800005];
    priority_queue<node> q;
    unordered_map<string, int> p;
    cin >> n;
    int cnt = n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        if (!p[s[i]])
            p[s[i]] = ++cnt;
    }
    vector<vector<Node> > g(cnt + 5);
    for (int i = 1; i <= n; i++) {
        g[i].push_back({p[s[i]], 0});
        g[p[s[i]]].push_back({i, 0});
    }
    cin >> m;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    cin >> T;
    while (T--) {
        int S, T;
        cin >> S >> T;
        vector<int> dis(cnt + 5, -1);
        q.push({S, 0});
        dis[S] = 0;
        while (!q.empty()) {
            node t = q.top(); q.pop();
            int u = t.u;
            for (Node i : g[u]) {
                int v = i.v, w = i.w;
                if (dis[v] == -1 || dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    q.push({v, dis[v]});
                }
            }
        }
        cout << dis[T] << '\n';
    }
}

signed main() {
    int T;
    cin >> T;
    for (int Case = 1; Case <= T; Case++)
        solve(Case);
    return 0;
}