fork(1) download
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<stack>
  4. using namespace std;
  5. #define INF 1145141919810
  6.  
  7. long long s[20][20][2],n,m,a,b,c,d,e,f,g[20],r;
  8. stack<int>S;
  9.  
  10. void dfs(){
  11. if(S.size()==n && s[S.top()][1][0]!=0 && r+s[S.top()][1][0]<=s[S.top()][1][1]){
  12. r+=s[S.top()][1][0];
  13. if(r==e){f++;}
  14. if(r<e){f=1;e=r;}
  15. r-=s[S.top()][1][0];
  16. return;
  17. }
  18. for(int i=1;i<=n;i++){
  19. if(s[S.top()][i][0]!=0 && g[i]==0 && r+s[S.top()][i][0]<=s[S.top()][i][1]){
  20. g[i]=1;
  21. r+=s[S.top()][i][0];
  22. S.push(i);
  23. dfs();
  24. }
  25. }
  26. int h=S.top();
  27. g[h]=0;
  28. S.pop();
  29. r-=s[S.top()][h][0];
  30. return;
  31. }
  32.  
  33. int main(){
  34. cin>>n>>m;
  35. for(int i=1;i<=m;i++){
  36. cin>>a>>b>>c>>d;
  37. s[a][b][0]=c;s[a][b][1]=d;
  38. s[b][a][0]=c;s[b][a][1]=d;
  39. }
  40. e=INF;f=0;
  41. g[1]=1;
  42. S.push(1);
  43. dfs();
  44. if(e!=INF){cout<<e<<' '<<f<<endl;}
  45. else{cout<<"IMPOSSIBLE"<<endl;}
  46. return 0;
  47. }
Success #stdin #stdout 0s 3472KB
stdin
3 3
1 2 1 6
2 3 2 6
3 1 3 6
stdout
6 2