{"problem":{"name":"[THUPC 2023 决赛] 百合","description":{"content":"你落在一个巨大的葡萄架上，上面一共有 $2^k$ 朵百合花和 $m$ 条葡萄藤。其中，百合花编号为 $0$ 到 $2^k-1$ 的整数，第 $i$ 条葡萄藤连接了编号为 $x_i, y_i$ 的百合花。 你可以花费 $c_i$ 的时间通过第 $i$ 条葡萄藤，也就是从 $x_i$ 走到 $y_i$，或者反过来；还可以花费 $a_k$ 的时间从 $x$ 闪现到 $y$，其中 $x, y$ 是任意两","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9377"},"statements":[{"statement_type":"Markdown","content":"你落在一个巨大的葡萄架上，上面一共有 $2^k$ 朵百合花和 $m$ 条葡萄藤。其中，百合花编号为 $0$ 到 $2^k-1$ 的整数，第 $i$ 条葡萄藤连接了编号为 $x_i, y_i$ 的百合花。\n\n你可以花费 $c_i$ 的时间通过第 $i$ 条葡萄藤，也就是从 $x_i$ 走到 $y_i$，或者反过来；还可以花费 $a_k$ 的时间从 $x$ 闪现到 $y$，其中 $x, y$ 是任意两朵百合花，$k$ 是它们在二进制表示下不同的比特数。例如，$3$ 的二进制表示是 $011$，$5$ 的二进制表示是 $101$，它们有两位不同，因此从 $3$ 闪现到 $5$ 花费的时间是 $a_2$。\n\n假设你恰好落在编号为 $s$ 的百合花上，求从 $s$ 出发到每一朵百合花所需要的最短时间。\n\n## Input\n\n第一行包含三个正整数 $k,m,s$，其含义如题目描述。\n\n第二行包含 $k$ 个非负整数 $a_i$，表示通道花费的时间。\n\n第 $3$ 至第 $(m+2)$ 行每行三个非负整数 $x_i,y_i,c_i$。\n\n## Output\n\n输出一行 $2^k$ 个数 $D_i$（$0 \\leq i \\leq 2^k-1$），空格隔开，其中 $D_i$ 表示从 $s$ 到 $i$ 的最短时间。\n\n[samples]\n\n## Background\n\n葡萄藤上开不出百合花。\n\n## Note\n\n**【数据范围】**\n\n对于所有测试数据，$1 \\le k \\leq 17$，$1 \\le m \\leq 2 \\times 10^5$，$0 \\leq s,x_i,y_i \\leq 2^k - 1$，$0 \\le a_i, c_i \\leq 2^{30} - 1$。\n\n**【题目来源】**\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。\n\n题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9377","tags":["2023","O2优化","最短路","THUPC"],"sample_group":[["3 6 2\n17 14 11 \n0 2 3\n4 2 9\n2 2 1\n2 2 6\n7 0 5\n4 2 9\n","3 14 0 17 9 11 17 8\n"]],"created_at":"2026-03-03 11:09:25"}}