记录编号	594740	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	2.041 s
提交时间	2024-10-04 19:19:47	内存使用	6.11 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=1e9+1;
int n,m,q,dp[110][110][110],v[110],v2[110],yh[110];
bool cmp(int x,int y)
{
    return v[x]<v[y];
}
int ef(int x)
{
    int l=0,r=n,ans=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(v2[mid]<=x)
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return ans;
}
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]);
        v2[i]=v[i];
    }
    sort(v2+1,v2+n+1);
    for(int i=1;i<=n;i++)
    {
        yh[i]=i;
    }
    sort(yh+1,yh+n+1,cmp);
    for(int k=0;k<=n;k++)
    {
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			dp[k][i][j]=1e9+1;
			}
		}
	}
    for(int i=1;i<=m;i++)
    {
        int x,y,l;
        scanf("%d%d%d",&x,&y,&l);
        dp[0][x][y]=min(dp[0][x][y],l);
        dp[0][y][x]=min(dp[0][y][x],l);
    }
    for(int k=0;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            dp[k][i][i]=0;
        }
    }
    /*for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		dp[0][i][j]=0;
		}
	}*/
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j) continue;
                dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][yh[k]]+dp[k-1][yh[k]][j]);
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        int s,c,d;
        scanf("%d%d%d",&s,&c,&d);
        int b=ef(c);
        int sum=0;
        for(int j=1;j<=n;j++)
        {
            if(j!=s&&dp[b][s][j]<=d) sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}