[THUPC 2023 决赛] 百合

Luogu
IDLGP9377
Time2000ms
Memory512MB
DifficultyP5
2023O2优化最短路THUPC
你落在一个巨大的葡萄架上,上面一共有 $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$ 是任意两朵百合花,$k$ 是它们在二进制表示下不同的比特数。例如,$3$ 的二进制表示是 $011$,$5$ 的二进制表示是 $101$,它们有两位不同,因此从 $3$ 闪现到 $5$ 花费的时间是 $a_2$。 假设你恰好落在编号为 $s$ 的百合花上,求从 $s$ 出发到每一朵百合花所需要的最短时间。 ## Input 第一行包含三个正整数 $k,m,s$,其含义如题目描述。 第二行包含 $k$ 个非负整数 $a_i$,表示通道花费的时间。 第 $3$ 至第 $(m+2)$ 行每行三个非负整数 $x_i,y_i,c_i$。 ## Output 输出一行 $2^k$ 个数 $D_i$($0 \leq i \leq 2^k-1$),空格隔开,其中 $D_i$ 表示从 $s$ 到 $i$ 的最短时间。 [samples] ## Background 葡萄藤上开不出百合花。 ## Note **【数据范围】** 对于所有测试数据,$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$。 **【题目来源】** 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2023)决赛。 题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。
Samples
Input #1
3 6 2
17 14 11 
0 2 3
4 2 9
2 2 1
2 2 6
7 0 5
4 2 9
Output #1
3 14 0 17 9 11 17 8
API Response (JSON)
{
  "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$ 是任意两...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments