ZeroJudge 解題筆記：g308. pB. 跳跳布朗尼(Brownie)

作者：王一哲
日期：2025年11月3日


ZeroJudge 題目連結：g308. pB. 跳跳布朗尼(Brownie)

解題想法

將傳送門狀態存入串列 portal，將每格的布朗尼數量存入串列 brownie。起始位置為 cur，會先拿到這格的布朗尼，更新拿到的布朗尼總數 cnt，再從 protal 讀取傳送的目的地 nxt，將用過的傳送門改成 -1。用 while 迴圈重複以上的過程，直到 nxt 為 -1 時停止。

Python 程式碼

使用時間約為 25 ms，記憶體約為 3.4 MB，通過測試。

n, t = map(int, input().split())
portal = list(map(int, input().split()))
brownie = list(map(int, input().split()))
cur = t  # 目前的位置
cnt = brownie[cur]  # 拿到的布朗尼總數，預設為目前位置的數量
brownie[cur] = 0  # 將目前位置的布朗尼總數歸零
nxt = portal[cur]  # 下一個位置
portal[cur] = -1  # 將目前位置要傳送的位置設成 -1，代表已經走過這格
while nxt != -1:  # 當 nxt 不等於 -1 時繼續執行
    cur = nxt  # 更新 cur
    cnt += brownie[cur]  # 加上目前位置的數量
    brownie[cur] = 0  # 將目前位置的布朗尼總數歸零
    nxt = portal[cur]  # 下一個位置
    portal[cur] = -1  # 將目前位置要傳送的位置設成 -1，代表已經走過這格
print(cnt)  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n, t; scanf("%d %d", &n, &t);
    int portal[n], brownie[n];
    for(int i=0; i<n; i++) scanf("%d", &portal[i]);
    for(int i=0; i<n; i++) scanf("%d", &brownie[i]);
    int cur = t, cnt = brownie[t], nxt = portal[t];
    brownie[cur] = 0;
    portal[cur] = -1;
    while(nxt != -1) {
        cur = nxt;
        cnt += brownie[cur];
        brownie[cur] = 0;
        nxt = portal[cur];
        portal[cur] = -1;
    }
    printf("%d\n", cnt);
    return 0;
}