C++11(clang++ 3.9) 解法, 执行用时: 1112ms, 内存消耗: 736K, 提交时间: 2018-11-03 14:58:07

#include <cstdio>
#include <cstring>
#define F(i,x,y) for(int i=x;i<=y;++i)

using namespace std;

const int M=30;
int from[M],to[M],val[M],fa[M];
int n,m,q;
int A[10010],B[10010],ans[10010];

int G(int x){
	return fa[x]==x?x:G(fa[x]);
}

void dfs(int x,int s,int t){
	if(t==n-1){
		F(i,1,q){
			if(s>=A[i]&&s<=B[i]){
				ans[i]++;
			}
		}
		return ;
	}
	if(x==m+1) return ;
	
	dfs(x+1,s,t);
	int fx=G(from[x]),fy=G(to[x]);
	if(fx!=fy){
		fa[fx]=fy;
		dfs(x+1,s+val[x],t+1);
		fa[fx]=fx;
	}
}

int main(){
    scanf("%d%d",&n,&m);
    F(i,1,n) fa[i]=i;
    F(i,1,m){
    	scanf("%d%d%d",&from[i],&to[i],&val[i]);
	}
	
	scanf("%d",&q);
	F(i,1,q){
		scanf("%d%d",&A[i],&B[i]);
	}
	dfs(1,0,0);
	F(i,1,q) printf("%d\n",ans[i]);
    return 0;
}