1996 . 傳送門

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

60.9% (14/23)

Submission's AC Ratio

33.7% (100/297)

Tags

CKcon 2017-CKcon-fin IOIstyle shortest-path

Description

遙遠的外星世界中，外星人建立了十分複雜的傳送門聯絡網，方便外星人們在不同的傳送點間移動。

在編號為0到N-1的傳送點之間，外星人根據不同的交通需求，所建造的傳送門一共分為三類：第零型、第一型與第二型。每個傳送門會運作於兩個固定的傳送點a, b之間，如果有任何東西進入傳送點a一端，傳送門會將其運送到b一端，反過來也可以通行。由於外星人的世界十分龐大，傳送點與傳送門的數量都非常多，甚至有可能兩個傳送點之間有很多個傳送門連接。然而，由於某些傳送門建造的技術原因，在外星人的世界中，第二型的傳送門的數量不會超過傳送點的數量。

三類傳送門中，第零型是最舊的外星科技，而第二型是最新的。第二型的傳送門所能傳送的物件數量最多、第一型其次、第零型最少。然而，使用傳送門所需要收取的卡梅（外星人的貨幣單位）數也與傳送門的種類有關：第零型可以免費使用、第一型每次使用要收8卡梅、第二型則是16卡梅。

今天要講的故事，主角是　　，是個專門維護傳送門聯絡網秩序的外星人。

要知道，以外星人的高科技，傳送門基本上是沒有甚麼維護問題的。然而，傳送點就不一樣了：外星人們要使用傳送門的時候，如果沒有依照正確的方式使用，會造成傳送點暫時堵塞，可以從傳送門出來但是進不去。因此，　　常常需要對傳送點進行維修。
不幸地，維修所需要的工具非常複雜且脆弱，以至於只有一個特定的「大本營傳送點」（也就是編號為0的傳送點）附近有辦法保存這些工具；而且每次維修完一個傳送點，就需要回到大本營傳送點將所有工具進行維護後才能再次維修。

因為維修的工作非常緊急，所以一旦收到某個傳送點堵塞的報告，他必須從大本營傳送點出發，先經由一系列的傳送門抵達堵塞的傳送點進行維修，再經由一系列的傳送門回到大本營傳送點。過程間所有傳送門收取的費用，　　必須先自己代墊，之後再向外星主管單位（　　　）申請經費。然而，外星主管單位可不會隨便批准　　的經費申請：如果　　申請的經費比來回最少需要的卡梅數還多的話，主管單位會認為　　想要藉機牟利，就不會批准　　的申請。因此，對於每次傳送點堵塞的事件，　　都會先自己算好要怎麼樣可以用最少卡梅在大本營傳送點和堵塞的傳送點之間來回。

然而，有時候從大本營傳送點到堵塞的傳送點間沒有辦法只經由傳送門抵達。這種情況就不在　　的負責範圍內了，所以　　可以很輕鬆的待在大本營傳送點休息。

你，一個研究外星文明的人，無意中發現了傳送門聯絡網的完整結構圖和　　的所有計算結果。為了研究這個外星文明的發展度，你決定先自己用結構圖算出所有的結果，以方便驗證　　有沒有算錯。

Input Format

本題沒有輸入，如果你輸入了任何東西，可能會導致各種不可預期的結果。

請#include "lib1996.h"之後實作下列兩個函數。

void init(int N, int M, int A[], int B[], int K[]);：評測系統將會在執行的一開始呼叫這個函式，傳入正整數N、M，分別代表外星世界中傳送點的數量、傳送門的數量；以及長度為M的非負整數陣列A、B、K，代表傳送門的資訊：第i個傳送門運作於編號為A[i]與B[i]的傳送點之間，且型號為K[i]。（保證A[i] ≠ B[i]。）
int get_cost(int x);：呼叫完init後，將會連續呼叫Q次這個函式，傳入一個非負整數x，代表有一個事件發生在傳送點x的位置。這個函數必須回傳　　完成任務至少需要花多少卡梅。如果　　可以待在大本營傳送點休息，請回傳-1。

在程式執行當中，你可以任意修改A、B、K陣列當中的值。

對於所有的測資，$N,Q \leq 3\times 10^ 6; M\leq 10^ 7; K[i]\in \{0,1,2\}$。

子任務（測資） 額外限制 分數
1 (0) $K[i]=0$，保證所有任務都可以完成 1
2 (0~2) $K[i]=0$ 13
3 (3~5) $N,M,Q \leq 2000$ 12
4 (3~9) $N,M,Q \leq 3 \times 10^ 5$ 21
5 (10~12) $K[i]\in \{0,1\}$ 15
6 (13~15) $K[i]\in \{1,2\}$ 12
7 (0~18) 無 26

Output Format

本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。

Sample Input 1

注意：本題沒有輸入，本輸入為提供測試標頭檔（參見Hints）使用。
4 3 4
0 1 1
1 2 2
0 2 0
0
1
2
3

Sample Output 1

注意：本題沒有輸出，本輸出為提供測試標頭檔（參見Hints）使用。
0
16
0
-1

Hints

這裡有一個測試用的標頭檔，可以用來測試。
該標頭檔接受以下輸入，數字間皆以空白分隔：
第一行：N, M, Q；
接下來M行：$A[i],B[i],K[i]$；
接下來Q行：x；
對於每一次呼叫get_cost函數，此程式會輸出一行包含一個正整數，代表函數回傳的數值。

以下是一個保證格式正確（不會CE也不會RE、MLE）但只能讓你獲得1分的範例程式：

#include "lib1996.h"

int *A, *B, *K, M;

void init(int n, int m, int a[], int b[], int k[]) {
  A = a;
  B = b;
  M = m;
  K = k;
}

int get_cost(int x) {
  return K[M - 1];
}

你說你想知道那個維修的外星人叫做甚麼？太天真啦，外星人的名子只有外星人才看得到。

Problem Source

Judge / Description by Yihda Yol
建國中學106學年度校隊選拔：複試pC

Subtasks

No. Testdata Range Score
1 0 1
2 0~2 13
3 3~5 12
4 3~9 21
5 10~12 15
6 13~15 12
7 0~18 26

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 7500 614400 262144 1 2 7
1 9000 614400 262144 2 7
2 7500 614400 262144 2 7
3 1900 614400 262144 3 4 7
4 1900 614400 262144 3 4 7
5 1900 614400 262144 3 4 7
6 1900 614400 262144 4 7
7 1900 614400 262144 4 7
8 1900 614400 262144 4 7
9 1900 614400 262144 4 7
10 9500 614400 262144 5 7
11 12000 614400 262144 5 7
12 12000 614400 262144 5 7
13 12000 614400 262144 6 7
14 12000 614400 262144 6 7
15 12000 614400 262144 6 7
16 9500 614400 262144 7
17 9500 614400 262144 7
18 9500 614400 262144 7
Submit
Back to Top