记录编号	594722	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2024-10-04 18:04:22	内存使用	3.39 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 120;
const int inf = 10000000000000;
#define ll long long

struct node{
    int id,va;
}a[N];

int v[N],pv[N],ppv[N],kk;
ll dp[N][N][N];
int n,m,q;

bool cmp(node x,node y){
    return x.va<y.va;
}

int hf(int x){
    int l=1,r=kk,mid,ans=0;
    while(l<=r){
        mid=(l+r)/2;
        if(pv[mid]<=x) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

void Floyd(){
	for(register int hh=1;hh<=n;hh++){
        int k=a[hh].va;
        for(register int i=1;i<=n;i++){
            for(register int j=1;j<=n;j++){
                if(i==j) continue;
                dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][a[hh].id]+dp[k-1][a[hh].id][j]);
            }
		}
    }
}

int main(){
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
		scanf("%d",&v[i]);pv[i]=v[i];
	}
    sort(pv+1,pv+n+1);
    kk=unique(pv+1,pv+n+1)-pv-1;
    for(int i=1;i<=n;i++)
    v[i]=lower_bound(pv+1,pv+kk+1,v[i])-pv;
    for(int i=1;i<=n;i++){
//    	cout<<v[i]<<" ";
        a[i].id=i,a[i].va=v[i];
    }
//    cout<<endl;
    sort(a+1,a+n+1,cmp);
    for(int k=0;k<=kk;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[k][i][j]=inf;
			}
		}
	}
    for(int i=1;i<=m;i++){
        int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
        dp[0][x][y]=min(dp[0][x][y],(ll)z);
        dp[0][y][x]=min(dp[0][y][x],(ll)z);
    }
    Floyd();
    for(register int i=1;i<=q;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        int hh=hf(y),ans=0;
        for(register int i=1;i<=n;i++){
            if(i==x) continue;
            if(dp[hh][x][i]<=z) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}