Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("orase.in");
- ofstream fout("orase.out");
- int n, x, i, j, a[101][101], ap[101], minim;
- vector< pair<int, int> > l[101];
- vector<int> sol;
- bool stop;
- bool comp( pair<int, int>& a)
- {
- return a.second == j;
- }
- void afisare(int cost)
- {
- if(cost < minim)
- {
- minim = cost;
- fout.close();
- fout.open("orase.out", ios :: out);
- fout << minim << '\n';
- for(const auto it : sol)
- {
- fout << it << ' ';
- }
- fout << sol[0] << endl;
- }
- stop = true;
- }
- bool solutie()
- {
- j = 1;
- return sol.size() == n && (find_if(l[sol[n-1]].begin(), l[sol[n-1]].end(), comp) != l[sol[n-1]].end());
- }
- void backt(int crt, int cost = 0)
- {
- if(cost > minim)
- {
- return;
- }
- for(auto i = l[crt].begin(); i != l[crt].end() && !stop; i++)
- {
- if(!ap[i -> second] || i -> second == 1 && sol.size() == n)
- {
- ap[i -> second] = 1;
- sol.push_back(i -> second);
- if(solutie())
- {
- j = sol[n-1];
- afisare(i->first + cost + find_if(l[sol[0]].begin(), l[sol[0]].end(), comp)-> first);
- }
- else
- {
- backt(i -> second, cost + i -> first);
- }
- ap[i -> second] = 0;
- sol.pop_back();
- }
- }
- }
- void rezolvare()
- {
- for(int i = 1; i <= n; i++)
- {
- ap[i] = 1;
- sol.push_back(i);
- backt(i);
- stop = false;
- ap[i] = 0;
- sol.pop_back();
- }
- }
- int main()
- {
- fin >> n;
- minim = INT_MAX;
- for(i = 1; i <= n; i++)
- {
- for(j = 1; j <= n; j++)
- {
- fin >> x;
- if( x && i > j)
- {
- l[i].push_back({x,j});
- l[j].push_back({x,i});
- }
- }
- }
- for(int i = 1; i <= n; i++)
- {
- sort(l[i].begin(), l[i].end());
- }
- rezolvare();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement