2021 年百度之星·程序设计大赛 - 初赛一. 鸽子

本文主要是介绍2021 年百度之星·程序设计大赛 - 初赛一. 鸽子，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://acm.hdu.edu.cn/showproblem.php?pid=6998

考虑每次操作能对答案产生的影响
记每次操作为\(swap(a,b)\),dp[i]表示答案,初始化位-1表示状态不可达,开始时dp[k] = 0.

• a不可达
  • b可达 dp[v] = dp[u], dp[u] := dp[u] + 1.
  • b不可达 无影响.
• a可达
  • b可达 dp[v] = min(dp[v] + 1, dp[u]) dp[u] = min(dp[u] + 1,dp[v]).
  • b不可达 dp[u] = dp[v], dp[v] := dp[v] + 1.

const int maxn = 1e6 + 7;

int n, t, m, k;

int dp[maxn];

void solve() {
    cin >> t;
    while (t--) {
        cin >> n >> m >> k;
        memset(dp, -1, sizeof dp);
        dp[k] = 0;
        for (int i = 1, u, v; i <= m; i++) {
            cin >> u >> v;
            int su = dp[u], sv = dp[v];
            if (su == -1 && sv == -1) continue;
            if (su == -1) dp[v] = sv + 1, dp[u] = sv;
            if (sv == -1) dp[u] = su + 1, dp[v] = su;
            if (su != -1 && sv != -1) dp[u] = min(sv, su + 1), dp[v] = min(su, sv + 1);
        }
        for (int i = 1; i <= n; i++)
            i == n ? cout << dp[i] << "\n" : cout << dp[i] << " ";
    }
}

这篇关于2021 年百度之星·程序设计大赛 - 初赛一. 鸽子的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！