Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <cstring>
- #include <queue>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <utility>
- #include <bitset>
- #include <cstdlib>
- #include <sstream>
- #include <algorithm>
- #define MAXN 10
- #define INF 999999999
- #define LL long long
- #define PI pair<int,int>
- using namespace std;
- int B,C,N,best;
- vector<PI> A[MAXN];
- int func(int v,int mask,int c){
- if(v == B && mask == (1<<(N))-1){
- best = min(best,c);
- return 0;
- }
- int ans = INF;
- for(int k=0;k<A[v].size();k++){
- int w = A[v][k].first;
- int p = A[v][k].second;
- if(c + p > best)
- continue;
- if(w == B && (mask != (((1<<N)-1)^((1<<(B-1)))))){
- continue;
- }
- if(mask&(1<<(w-1)))
- continue;
- ans = min(ans,p+func(w,mask|(1<<(w-1)),c+p));
- }
- return ans;
- }
- int main(){
- int Q;
- cin >> Q;
- for(int i=0;i<Q;i++){
- cin>>B>>C>>N;
- for(int j=0;j<C;j++){
- int v,w,p;
- cin >> v >> w >> p;
- A[v].push_back(make_pair(w,p));
- A[w].push_back(make_pair(v,p));
- }
- best = INF;
- int ans = func(B,0,0);
- cout << ans << endl;
- for(int j=0;j<MAXN;j++)
- A[j].clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement