ZeroJudge A290: Training～Turing

"All roads lead to Rome."

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF inputs: each input consists of two positive integers, N and M (N ≤ 800, M ≤ 10000).
It means there are N cities and M roads!
Please note that the roads are directional!
Next, there are M lines, each containing 2 positive integers a and b (1 ≤ a, b ≤ N).
This means city a can reach city b.
The last line contains two positive integers A and B (1 ≤ A, B ≤ N).		If city A can reach city B, please output "Yes!!!". Otherwise, output "No!!!".
8 32
7 4
2 5
7 5
3 7
2 1
2 2
2 4
4 4
4 7
8 5
7 5
5 2
6 7
7 5
8 8
4 7
6 3
4 1
4 4
8 7
3 4
2 6
6 1
6 8
4 5
7 5
6 6
4 4
2 6
5 3
7 4
1 3
1 3		Yes!!!
ZeroJudge A290: Sample Input/Output

Thought Process

Use a Map<int, vector> to store which cities can reach which cities, and use BFS to find which cities can reach which cities. Each time entering BFS, you need to determine which cities have already been pushed back to the next starting point. If a city has already been pushed back as a starting point, it should not be pushed back again.

If you reach the destination city, output "Yes". If you encounter a starting point with an array length of 0, it means you can never reach the destination, so output "No".

Sample Code－ZeroJudge A290: Training～Turing

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

map<int, vector<int>>MAP;
int N, M, start, finish;

void BFS(vector<int>start)
{
    if (start.size() == 0)
    {
        cout << "No!!!\n";
        return;
    }
    vector<int>newStart;
    map<int, int>appear;
    for (int i = 0; i<start.size(); i++)
    {
        vector<int>step = MAP[start[i]];
        for (int j = 0; j<step.size(); j++)
        {
            if (step[j] == finish)
            {
                cout << "Yes!!!\n";
                return;
            }
            if (appear[step[j]] == 0)
            {
                appear[step[j]]++;
                newStart.push_back(step[j]);
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N >> M)
    {
        MAP.clear();
        for (int i = 0; i<M; i++)
        {
            int a, b;
            cin >> a >> b;
            MAP[a].push_back(b);
        }
        cin >> start >> finish;
        vector<int>v;
        v.push_back(start);
        BFS(v);
    }
}

//ZeroJudge A290
//Dr. SeanXD
Tags

Related Posts

Comments