ZeroJudge E999: Bonus

A dating game production company is celebrating its 10th anniversary by releasing a special game online. Whoever completes the game and achieves the best ending will win a grand prize of NT$10 million. The game's content is as follows:

一個男孩遇見了心儀的對象，參賽者要幫助這個男孩在每個階段進行事件選擇，選擇後會進入下一個階段，然後再進行選擇 …… 直至結局階段。結局為何，取決於玩家所經歷的階段和事件。所有的結局中，只有一個路線能達成最佳結局。

Due to cost considerations, the company decided to charge each participant a fee. They discussed the fee amount and eventually came up with a series of complex mathematical formulas for calculating the fee, with the total number of routes in the game being the most critical value. You are an employee of the company, and you are responsible for calculating the total number of routes, R.

The game's settings are as follows:

  1. The game has a total of N stages, with S0 being the initial stage and SN-1 being the final stage.
  2. For each stage Si, event Eij will lead the player to stage Sj.
  3. For any stage, the player can only experience it once. In other words, no event will allow the player to return to a previously experienced stage.
  4. Regardless of the choices made in between, the game always starts at S0 and ends at SN-1.
  5. The total number of routes, R, is not zero.
  6. There will be no duplicate events (at most one event connects any two stages).
ZeroJudge E999 題目解說

For example, in the above diagram, there are 7 different routes to reach SN-1.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
Each test case starts with a line containing two positive integers, N and E. N represents the number of stages, numbered from 0 to N-1, and E (where S-1 ≤ E ≤ 2×S) represents the number of events. Following this, there are E lines, each containing two integers, i and j, indicating that there is an event Eij from stage Si leading to stage Sj.For each test case, output a single positive integer R, which represents the total number of routes.
9 12
0 1
0 2
0 3
0 5
0 7
3 4
1 4
4 6
7 6
6 8
2 8
5 8		5
10 14
0 1
0 2
1 3
1 4
1 5
1 6
2 6
3 9
4 9
5 9
6 7
6 8
7 9
8 9		7
ZeroJudge E999 Sample Test Cases

Thought Process

Use BFS and a Map to record the points each stage can lead to. Declare an ans array initialized to 0, and set ans[0] to 1.

In BFS, update the ans value of the next point by adding the ans value of the current point. It is important to keep track of how many points need to be visited before reaching each point. When visiting a point, decrement the count of its predecessors. Only add the point to the BFS queue when all its predecessors have been visited.

The answer is the value of ans[N-1].

Sample Code－ZeroJudge E999: Bonus

#include <iostream>
#include <vector>
#include <map>
using namespace std;

map<int, vector<int>>MAP;
map<int, int>ans, previous;

pair<int, int> p (const int a, const int b) {
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

void BFS(const vector<int>start) {
    if (start.size() == 0) return;
    vector<int>newStart;
    for (int i = 0; i<start.size(); i++) {
        const int current = start[i];
        for (int j = 0 ; j<MAP[current].size(); j++) {
            const int next = MAP[current][j];
            previous[next]--;
            ans[next] += ans[current];
            if (previous[next] == 0) newStart.push_back(next);
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, E;
    cin >> N >> E;
    for (int i = 0; i<E; i++) {
        int a, b;
        cin >> a >> b;
        MAP[a].push_back(b);
        previous[b]++;
    }
    ans[0] = 1;
    vector<int>start;
    start.push_back(0);
    BFS(start);
    cout << ans[N-1] << "\n";
}

//ZeroJudge E999
//Dr. SeanXD

Tags

Related Posts

Comments