diancuoi
quoc14
plain_text
a month ago
3.8 kB
2
Indexable
Never
caidat
#include <iostream> using namespace std; int n, m; int a[50][50]; int start, endd; int queue[10000000]; int front, rear; int visit[50]; int res; int check[50]; void resetvisit() { for (int i = 1; i <= n; i++) { visit[i] = 0; } } void dfs(int x, int count) { if (x == endd) { if (count - 1 < res) { res = count - 1; } } visit[x] = 1; for (int i = 1; i <= n; i++) { if (visit[i] == 0 && a[x][i] == 1) { if (check[i] == 0) { dfs(i, count + 1); check[i] = 1; } else { dfs(i, count); } } if (a[x][i] == 1 && visit[i] == 1 && i == endd) { if (count < res) { res = count; } } } } void solve(int testcase) { cin >> n >> m; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; a[x][y] = 1; } /* for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << a[i][j] << " "; } cout << endl; } */ for (int i = 1; i <= n; i++) { check[i] = 0; } int ans = 0; resetvisit(); start = 1; endd = 2; res = 100; dfs(start, 0); cout << res << endl; resetvisit(); start = 2; endd = 1; res = 100; dfs(start, 0); cout << res << endl; } int main() { freopen("Text.txt", "r", stdin); int t; cin >> t; for (int i = 1; i <= t; i++) { solve(i); } return 0; } 4 6 7 1 3 3 4 4 5 5 1 4 2 2 6 6 3 9 11 1 3 3 4 4 2 2 5 5 3 3 6 6 1 2 7 7 8 8 9 9 1 12 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 16 144 3 9 10 3 1 14 6 10 12 2 10 9 11 6 12 11 16 11 3 1 14 12 5 10 15 7 1 15 9 16 6 12 8 16 14 8 13 4 2 8 5 11 16 15 10 16 16 3 8 5 12 6 11 12 4 3 11 10 14 3 9 12 10 5 15 11 13 3 2 5 7 11 4 12 6 4 14 13 8 9 3 2 4 6 4 14 15 2 16 7 13 10 4 8 13 9 3 14 14 9 8 1 4 1 10 11 2 16 1 9 7 13 7 6 9 3 14 11 1 11 12 7 5 15 8 15 4 5 11 4 13 1 2 6 4 10 9 1 4 9 14 5 3 15 14 2 15 1 11 7 15 12 5 14 2 7 16 6 8 6 12 10 6 5 9 6 13 6 6 1 1 7 14 15 10 8 2 13 3 8 6 14 2 10 16 14 15 6 9 5 6 9 11 3 8 12 5 4 1 8 6 7 1 5 15 16 2 14 3 12 7 1 13 5 3 16 7 8 7 10 14 7 7 16 9 11 9 10 5 1 1 16 10 4 6 16 10 7 7 3 11 1 2 12 12 13 13 15 15 10 4 15 5 8 16 4 8 13 7 12 6 8 7 2 4 13 10 14 15 13 15 3 11 15 6 15 16 10 1 6 7 5 8 4 10 6 1 13 #include <iostream> using namespace std; int n, m; int map[100][100]; int check[100]; int vs[100]; int minans; int kt; void DFS(int st, int ed) { vs[st] = 1; if (st == ed) kt = true; if (kt == true) return; for (int i = 1; i <= n; i++) if (check[i] == 1 && map[st][i] == 1 && vs[i] == 0) DFS(i,ed); } int checkk() { kt = false; for (int i = 1; i<=n; i++) vs[i] = 0; DFS(1,2); if (kt == false) return 0; else { for (int i = 1; i<=n; i++) vs[i] = 0; kt = false; DFS(2,1); } if (kt == false) return 0; return 1; } void backtrack(int index, int cost) { if (index == n + 1) { if (cost < minans && checkk() == 1) { minans = cost; } return; } if (cost >= minans) return; for (int i = 0; i <=1; i++) if (i == 0) backtrack(index + 1, cost); else { check[index] = 1; backtrack(index + 1, cost + 1); check[index] = 0; } } int main() { // freopen("input.txt","r",stdin); int ntc; cin >> ntc; for (int tc=1; tc<=ntc; tc++) { cin >> n >> m; for (int i = 0; i<= n+1; i++) for (int j = 0; j<= n+1; j++) map[i][j] = 0; for (int i = 1; i <= m; i++) { int xx, yy; cin >> xx >> yy; map[xx][yy] = 1; } minans = 99999; check[1] = 1; check[2] = 1; backtrack(3, 0); cout << minans + 2 << endl; } return 0; }
Leave a Comment