# 20250427 TTC 題解

### pA

author : paul
problem setter : blame

First Killed : ®Blameazu®┻━┻ ︵ヽ(\`Д´)ﾉ︵ ┻━┻

:::success
給定一個 $N$ 點 $M$ 邊的無向圖，問跟點 $1$ 距離 $> 6$ 的有幾個點(每一條邊的距離為 $1$)
無連通視為距離 $\infty$
:::

:::spoiler 子任務2
鍊狀圖

隨便dfs即可
:::

:::spoiler 滿分解
放輕鬆，BFS即可

vector<int> dis(n+1, -1);
dis[1] = 0;
queue<int> qq({1});
while(qq.size()) {
    int now = qq.front();
    qq.pop();
    for(auto &d : g[now]) if(dis[d] == -1) {
        dis[d] = dis[now] + 1;
        qq.push(d);
    }
}
cout << count_if(dis.begin()+1, dis.end(), [&](int x) 
                 {return x > 6 || x == -1;}) << '\n';

:::

### pB

author : blame
problem setter : blame

First Killed : ®Blameazu®┻━┻ ︵ヽ(\`Д´)ﾉ︵ ┻━┻

:::success
給一張 $N$ 點 $M$ 邊的有向圖
求有多少點在環上，或者可以從某個環上走到。
:::

:::spoiler 子任務二
大概是dfs隨便做一做都有
:::

:::spoiler 滿分解
拓樸排序後剩下來沒 visited 過的點即為答案
拓樸排序可以採用Kahn's Algorithm
:::

:::spoiler bonus
有人硬砸 SCC 把他砸過去了 ==
:::

### pC

author : charhao
problem setter : charhao

First Killed : KCC

:::success
給 $n$ 點 $m$ 邊的無向連通圖，每條邊上都有一個邊權 $w_i$

定義一條 $a$ 到 $b$ 的"最佳路徑"為 $a$ 到 $b$ 所有路徑中最大邊權最小的那一條路徑

定義 $a$ 到 $b$ 的距離為 $a$ 到 $b$ 的最佳路徑上最大的邊權

求第 $K$ 小的距離為多少
:::

:::spoiler 滿分解
先從小到大排序邊權，然後用DSU維護第 $i$ 條邊可以讓多少點對的答案是 $w_i$，重複直到合起來的總點對數量超過 $K$
:::

### pD

source : https://www.luogu.com.cn/problem/P5905
problem setter : blame

First Killed :

:::success
給定一張 $N$ 點 $M$ 邊的帶權有向圖

問所有點之間的最短路

假如圖中有負環，請直接輸出 "-1"
:::

:::spoiler 子任務 2
手動判斷
:::

:::spoiler 子任務 3
暴力解，可以採用 floyd-warshall
:::

:::spoiler 子任務 4
做 $N$ 次 Dijkstra
:::

:::spoiler 滿分解
這題是 Johnson 全點對最短路的裸題
先對圖做一次 Bellman Ford 判斷負環
(這邊要開一個虛擬點 $0$ 對所有的點加邊權為 $0$ 的邊)
再做 $N$ 次Dijkstra，
但因為 Dijkstra 在負權圖上會吃WA or 吃TLE
所以要用勢能分析的方式解決 (詳細證明網路上找都有)

複雜度 $O(NM + N(N+M)log(M))$
:::

:::spoiler bonus
這題嚴格比對
:::

## Conclusion and Some Complaints

除了 charhao 出的 pC 外
其他題目皆有分子任務出來
撈子任務其實是一個技巧
希望下次可以看到各位更努力的撈分
這樣才能使競爭更加激烈且健康 :)