區間建邊？那就用線段樹啊！
Last updated 2 years ago
Was this helpful?
考慮（Codeforces 786B)
給定一張 nnn 個點的有向圖，接下來有以 qqq 次加邊的操作每次操作會是以下三種1 u v w1\ u \ v \ w1 u v w :從 uuu 到 vvv 建一條權重為 www 的邊。2 u l r w2\ u \ l \ r \ w2 u l r w :從 uuu 到 [l,r][l,r][l,r] 區間內所有點建一條權重為 www 的邊。3 v l r w3\ v \ l \ r \ w3 v l r w :從 [l,r][l,r][l,r] 區間內所有點到 uuu 建一條權重為 www 的邊。輸出從原點 sss 到所有點的最短路徑長1≤n, q≤1051 \le n, \ q \le 10^51≤n, q≤105
給定一張 nnn 個點的有向圖，接下來有以 qqq 次加邊的操作
每次操作會是以下三種
1 u v w1\ u \ v \ w1 u v w :從 uuu 到 vvv 建一條權重為 www 的邊。
2 u l r w2\ u \ l \ r \ w2 u l r w :從 uuu 到 [l,r][l,r][l,r] 區間內所有點建一條權重為 www 的邊。
3 v l r w3\ v \ l \ r \ w3 v l r w :從 [l,r][l,r][l,r] 區間內所有點到 uuu 建一條權重為 www 的邊。
輸出從原點 sss 到所有點的最短路徑長
1≤n, q≤1051 \le n, \ q \le 10^51≤n, q≤105
