记录编号	595054	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	袁书杰	是否通过	通过
代码语言	C++	运行时间	1.975 s
提交时间	2024-10-07 16:49:38	内存使用	28.73 MiB

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    struct node{
        int number;
    	int value;
    }a[1000005];
    struct node1{
    	int s;
    	int c;
    	int d;
    	int number;
    }now[1000005];
    int n,m,q,dis[1005][1005],dis1[1005][1005],ans=1,output_ans[1000005];
    bool cmp(node a1,node a2){
        return a1.value<a2.value;
    }
    bool cmp1(node1 now1,node1 now2){
        return now1.c<now2.c;
    }
    void work(int now){
    	for(int i=1;i<=n;i++){
    		if(now!=i){
    			for(int j=1;j<=n;j++){
    				if(now!=j&&i!=j){
    					dis[i][j]=min(dis[i][j],dis[i][now]+dis[now][j]);
    				}
    			}
    		}
    	}
    }
    signed main(){
        freopen("snackstore.in","r",stdin);
        freopen("snackstore.out","w",stdout);
        ios::sync_with_stdio(false);
        cin.tie(0),cout.tie(0);
        cin>>n>>m>>q;
        for(int i=1;i<=n;i++){
         	cin>>a[i].value;
         	a[i].number=i;
        }
        sort(a+1,a+n+1,cmp);
        memset(dis,0x3f,sizeof(dis));
        memset(dis1,0x3f,sizeof(dis1));
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=n;j++){
        		if(i!=j){
        			dis[i][j]=dis1[i][j]=1e9+1;
        		}
        	}
        }
        for(int i=1;i<=m;i++){
         	int u,v,w;
         	cin>>u>>v>>w;
         	if(u==v){
         		continue;
         	}
         	dis[u][v]=min(dis[u][v],w);
         	dis[v][u]=min(dis[v][u],w);
        }
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=n;j++){
        		dis1[i][j]=dis[i][j];
        	} 
        	sort(dis1[i]+1,dis1[i]+n+1);
        }
        for(int i=1;i<=q;i++){
        	cin>>now[i].s>>now[i].c>>now[i].d;
        	now[i].number=i;
        }
        sort(now+1,now+q+1,cmp1);
        for(int i=1;i<=q;i++){
        	while(now[i].c>=a[ans].value&&ans<=n){
        		work(a[ans++].number);
        		for(int i=1;i<=n;i++){
        			for(int j=1;j<=n;j++){
        				dis1[i][j]=dis[i][j];
        			} 
        			sort(dis1[i]+1,dis1[i]+n+1);
        		}
        	}
       		output_ans[now[i].number]=upper_bound(dis1[now[i].s]+1,dis1[now[i].s]+n+1,now[i].d)-dis1[now[i].s]-1;
       	}
       	for(int i=1;i<=q;i++){
    		cout<<output_ans[i]<<'\n';
       	}
        return 0;
    }