[伯俊/C+]2005号ACM Craft

[伯俊/C+]2005号ACM Craft

1.質問

西暦2012年!ついに2年間、多くの国民が待ち受けるゲームACMクラフト(Association of Construction Managerクラフト)が発売された.
このゲームは以前のゲームとは異なり、ACMクラフトは活気に満ちたゲームを行うために建物を建てる順番を決めていない.つまり、1ゲーム目と2ゲーム目で建物を建てる順番が異なる場合があります.試合が始まるたびに、建物を建てる順番が与えられます.また、どの建物にもDelayがあり、建て始めから完成まであります.

上の例を見てください.
今回のゲームでは以下の建設順序ルールが与えられている.1号棟が完成したら、2号と3号の建設を始めることができます.(同時進行可能)また、4号棟を建てるためには、2号棟と3号棟がすべて完成しなければ、4号棟の建設が開始されません.
そのため、4号棟の建設を完了するには、まず最初の1号棟を建てるのに10秒かかります.また、2号棟と3号棟が同時に建設を開始すれば、2号棟は1秒後には完成するが、3号棟はまだ完成していないため、4号棟は建設できない.3号棟が完成すると、その時は4号棟を建てることができ、4号棟が完成するのに120秒かかります.
プロゲーマーの崔柏俊は、恋人とのデートの費用を用意するため、西江大学杯ACM Craft大会に出場した.崔伯俊は華麗なコントロール能力を持っているので、すべての試合で特定の建物を建てさえすれば、必ずゲームで勝つことができる.しかし、ゲームごとに特定の建物を建てる順番が違うので、崔伯俊はがっかりした.白俊のためにプログラムを作り、最も速い時間で特定の建物を建てるのに必要な最短時間を見つけた.

2.入力

第1行は、試験例の個数Tを与える.各テストの例は次のとおりです.第1行は、建築個数Nと建築間の建築順序規則の合計個数Kを与える.(建物番号は1番からN番まであります)
第2列の各建物の建設に要する時間Dは空白である.3行目からK+2行目まで、建設手順X Yが与えられる.(これはX棟を建ててY棟を建てることが可能であることを意味します)
最後の列は白俊が勝利のために建てた建物の番号Wを示した.

3.出力

建物Wの完成に要する最小時間を出力する.快適な建物を建てる命令を下すには時間がかからないと仮定します.
建設の順序はすべての建物が建てられることです.

4.制限

2 ≤ N ≤ 1000

1 ≤ K ≤ 100,000

1 ≤ X, Y, W ≤ N

0≦D≦100000、Dは整数

5.解答

位相位置合わせ質問

・操作と似ています.

各建物の建設に要する時間を配列に格納する.

各建物の先行関係を入力graph並び

先行関係のある建物の数を増やす.

車数0の建物のd[i]自分で造るのに要する時間にリセットしてキューに挿入します.

車数0の建物に連なる建物の数を減らす.

減少回数が0の場合、その建物をキューに挿入する.

建物の建設に要する時間はd[next] = max(d[next], d[now] + arr[next]

現在の建物w反復ドアを終了.

d[w]建築Wの完成に要する最小時間.

5.最初のコードと異なる点

出力が必要

・d[w]ですが、出力したd配列の中での最値を修正しました.

6.コード

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;


int n, m, w;
vector<int> answer;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t;
  cin >> t;
  for (int tc = 0; tc < t; tc++) {
    int arr[1001];
    int indegree[1001] = {0, };
    vector<int> graph[1001];
    int d[1001] = {0 ,};

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
      cin >> arr[i];
    }
    
    for (int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      graph[a].push_back(b);
      indegree[b]++;
    }

    cin >> w;

    queue<int> q;

    for (int i = 1; i <= n; i++) {
      if (indegree[i] == 0) {
        q.push(i);
        d[i] = arr[i];
      }
    }

    while (!q.empty()) {
      int now = q.front();
      if (now == w) break;
      q.pop();

      for (int i = 0; i < graph[now].size(); i++) {
        int next = graph[now][i];
        if (--indegree[next] == 0) q.push(next);

        d[next] = max(d[next], d[now] + arr[next]);
      }
    }
    
    answer.push_back(d[w]);
  }
  
  for (int i = 0; i < t; i++) {
    cout << answer[i]<<endl;
  }
}