Untitled
unknown
plain_text
2 years ago
1.0 kB
6
Indexable
#include <iostream> using namespace std; int n,m; int kq; int duongdi[21][21]; int visit[21]; int sum; int dem[21]; void backtrack(int st){ if(visit[st] > 2) return; if(visit[1] == 2 ){ if(visit[2] == 1){ if(sum < kq) kq = sum; return; } return; } for(int i = 0; i < dem[st]; i++){ if(visit[duongdi[st][i]] < 2){ visit[duongdi[st][i]]++; if(visit[duongdi[st][i]] == 1) sum++; backtrack(duongdi[st][i]); visit[duongdi[st][i]]--; if(visit[duongdi[st][i]] == 0) sum--; } } } int main(){ freopen("input.txt","r",stdin); int T; cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> n >> m; for(int i = 1; i<= n; i++){ visit[i] = 0; dem[i] = 0; } visit[1] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ duongdi[i][j] = 0; } } for(int i = 0; i < m; i++){ int x, y; cin >> x; cin >> y; duongdi[x][dem[x]] = y; dem[x]++; } kq = 1000; sum = 1; backtrack(1); cout << kq << endl; } return 0; }
Editor is loading...