CodeChef-CLIQUED Bear and Clique Distances

前言

又被CC续了一晚上…感觉CC的数据好坑啊…

题目描述

分析

由于古城间的边数已经达到平方级,这样直接暴力地去加边是一定不能承受的。因此我们要充分利用古城间距离都是X的性质。会发现:如果离S最近的古城t距离为d,那么S到其他古城的距离就是d+X。因此我们可以不加入古城间的边,而是每次一个古城作为更新点的时候,直接用d+X更新其他古城。但是这样更新次数容易退化为平方级的。思考一下会发现,S到任一城市的最短路只可能是两种情况:

  1. 不经过古城间的路
  2. 经过古城间的路(至多走1条)

所以我们可以先从S开始跑一遍最短路,这一遍我们不经过任何古城,那么离S最近的古城距离已经求出了。至此我们求出了S到所有古城的距离,我们再用这些古城去更新其他点的最短路。
这道题Dijkstra+堆优化会被卡T(我不知道为什么),然后改成SPFA就可以AC了!
(网上也有建中间点的做法,类似CF的那道拓扑排序)

参考程序

#define fir first
#define sec second
typedef long long LL;
const LL INF = 0x7f7f7f7f7f7f7f7f;
struct Edge {
    int to, cost, next;
} E[MAXN << 1];

int T, N, K, X, M, S, last[MAXN], tote;
LL dist[MAXN];
bool in_que[MAXN];

namespace FastIO {
    template <typename T>
    void read(T & x) {
        x = 0; register char ch = getchar();
        for (; ch < '0' || ch > '9'; ch = getchar());
        for (; ch >= '0' && ch <= '9'; x = (x << 3) + (x << 1) + (ch ^ '0'), ch = getchar());
    }
}
inline void add_edge(int u, int v, int c) {
    E[++tote].to = v, E[tote].cost = c, E[tote].next = last[u], last[u] = tote;
    E[++tote].to = u, E[tote].cost = c, E[tote].next = last[v], last[v] = tote;
}
inline void init() {
    tote = 0;
    memset(last, 0, sizeof last);
    memset(in_que, 0, sizeof in_que);
    memset(dist, 0x7f, sizeof dist);
}
void solve();

int main() {
    FastIO::read(T);
    while (T--) solve();
    return 0;
}

void solve() {
    using FastIO::read;
    read(N), read(K), read(X), read(M), read(S);
    init();
    for (int i = 0, ai, bi, ci; i < M; i++) {
        read(ai), read(bi), read(ci);
        add_edge(ai, bi, ci);
    }
    dist[S] = 0;
    std::queue<int> Q;
    Q.push(S);
    // 第一遍SPFA,求出S到最近的古城的距离以及不经过古城到其他城市的距离
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = last[u], v; i; i = E[i].next)
            if (dist[u] + E[i].cost < dist[v = E[i].to]) {
                dist[v] = dist[u] + E[i].cost;
                // 不加入古城
                if (v > K && !in_que[v]) in_que[v] = true, Q.push(v);
            }
        in_que[u] = false;
    }
    LL mind = INF;
    for (int i = 1; i <= K; i++) mind = std::min(mind, dist[i]);
    if (mind != INF) {
        // 求出S到所有古城的最短距离
        for (int i = 1; i <= K; i++) {
                dist[i] = std::min(dist[i], mind + X);
                Q.push(i);
            }
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (int i = last[u], v; i; i = E[i].next)
                if (dist[u] + E[i].cost < dist[v = E[i].to]) {
                    dist[v] = dist[u] + E[i].cost;
                    if (!in_que[v]) in_que[v] = true, Q.push(v);
                }
            in_que[u] = false;
        }
    }
    for (int i = 1; i <= N; i++) printf("%lld ", dist[i]);
    putchar('\n');
}

总结

这题需要对于古城的性质进行充分思考,任何不充分的思考都会增加额外的运行时间。不过卡Dijkstra我也是搞不太懂,理论上说不应该去卡SPFA吗?也许是我对这两类最短路算法还不够了解吧。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注