Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2014
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <queue>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <utility>
  9. #include <bitset>
  10. #include <cstdlib>
  11. #include <sstream>
  12. #include <algorithm>  
  13. #define MAXN 10
  14. #define INF 999999999
  15. #define LL long long
  16. #define PI pair<int,int>
  17.  
  18. using namespace std;
  19.  
  20. int B,C,N,best;
  21. vector<PI> A[MAXN];
  22.  
  23. int func(int v,int mask,int c){
  24.  
  25.   if(v == B && mask == (1<<(N))-1){
  26.     best = min(best,c);
  27.     return 0;
  28.   }
  29.  
  30.   int ans = INF;
  31.  
  32.   for(int k=0;k<A[v].size();k++){
  33.     int w = A[v][k].first;
  34.     int p = A[v][k].second;
  35.     if(c + p > best)
  36.       continue;
  37.  
  38.     if(w == B && (mask != (((1<<N)-1)^((1<<(B-1)))))){
  39.       continue;
  40.     }
  41.     if(mask&(1<<(w-1)))
  42.       continue;
  43.  
  44.     ans = min(ans,p+func(w,mask|(1<<(w-1)),c+p));
  45.   }
  46.   return ans;
  47. }
  48.  
  49. int main(){
  50.  
  51.   int Q;
  52.   cin >> Q;
  53.   for(int i=0;i<Q;i++){
  54.     cin>>B>>C>>N;
  55.     for(int j=0;j<C;j++){
  56.       int v,w,p;
  57.       cin >> v >> w >> p;
  58.       A[v].push_back(make_pair(w,p));
  59.       A[w].push_back(make_pair(v,p));
  60.     }
  61.  
  62.     best = INF;
  63.     int ans = func(B,0,0);
  64.     cout << ans << endl;
  65.    
  66.     for(int j=0;j<MAXN;j++)
  67.       A[j].clear();
  68.   }
  69.                
  70.   return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement