22612023-01-06 14:03:06kohumarkTom és Jerry2 (60)cpp17Runtime error 9/60474ms63408 KiB
#include <bits/stdc++.h>
using namespace std;

void fjerry(int x, int d, bool visited[], set<int> hist, int pii, vector<vector<int>>& jerry, int n, set<int>& ctom)
{
    visited[x] = true;
    hist.insert(x);
    pii++;
    if (x == d) {
        for (int i = 0; i < n; i++){
			if(!hist.count(i)) ctom.erase(i);
	    }
	}
    else {
        for(int i = 0; i < (int)jerry[x].size(); i++)
            if (!visited[jerry[x][i]])
                fjerry(jerry[x][i], d, visited, hist, pii, jerry,n,ctom);
    }
    pii--;
    visited[x] = false;
	hist.erase(x);
}

void route(int x, int d, bool visited[], int pii, vector<vector<int>>& map, int& l)
{
    visited[x] = true;
    pii++;
    if (x == d && pii < l) l=pii; 
    else {
        for(int i = 0; i < (int)map[x].size(); i++)
            if (!visited[map[x][i]])
                route(map[x][i], d, visited, pii, map, l);
    }
    pii--;
    visited[x] = false;
}

int main(){
	cin.tie(NULL); ios::sync_with_stdio(NULL);
	int n, m, t, db, e;
	cin >> n >> m >> t >> db >> e; e--; t--;
	vector<vector<int>> tom; vector<vector<int>> jerry;
	tom.assign(n, vector<int>());
	jerry.assign(n, vector<int>());
	for(int i=0; i<m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		jerry[a].push_back(b);
		jerry[b].push_back(a);
		if(c==2&&b!=e&&a!=e){tom[a].push_back(b);tom[b].push_back(a);}
	}
	
	for(int i=0; i<db; i++){
		int x; cin >> x; x--;
		int pii=0;
		
		bool* visited = new bool[n];
		set<int> ctom;
		set<int> hist;
		for (int i = 0; i < n; i++){visited[i] = false; ctom.insert(i);}
		fjerry(x,e,visited,hist,pii,jerry,n,ctom);
		
		bool can=false;
		int lena=100000000; int lenb=100000000;
		for(auto it=ctom.begin(); it!=ctom.end(); it++){
			int d = *it + 1;
			pii=0;
			for(int i = 0; i < n; i++){visited[i] = false;}
			route(x,*it,visited,pii,jerry,lena);
			pii=0;
			for(int i = 0; i < n; i++){visited[i] = false;}
			route(t,*it,visited,pii,tom,lenb);
			if(lenb<=lena){cout << d << '\n'; can=true; break;}
		}
		
		if(!can) cout << '0' << '\n';
	}
}
SubtaskSumTestVerdictTimeMemory
base9/60
1Accepted0/03ms1824 KiB
2Runtime error0/0158ms62088 KiB
3Accepted2/22ms2280 KiB
4Accepted2/22ms2396 KiB
5Accepted2/219ms2640 KiB
6Accepted3/3384ms3004 KiB
7Time limit exceeded0/2460ms2744 KiB
8Time limit exceeded0/2449ms3204 KiB
9Time limit exceeded0/2469ms3376 KiB
10Time limit exceeded0/3474ms3920 KiB
11Time limit exceeded0/3462ms5348 KiB
12Time limit exceeded0/3469ms12628 KiB
13Runtime error0/359ms63408 KiB
14Runtime error0/359ms63340 KiB
15Runtime error0/361ms63140 KiB
16Runtime error0/354ms62900 KiB
17Runtime error0/350ms62736 KiB
18Runtime error0/361ms62516 KiB
19Runtime error0/471ms62488 KiB
20Runtime error0/487ms62464 KiB
21Runtime error0/568ms62444 KiB
22Runtime error0/565ms62428 KiB