记录编号	340263	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	yveh	是否通过	通过
代码语言	C++	运行时间	2.558 s
提交时间	2016-11-06 15:38:13	内存使用	33.65 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
char *ch=(char *)malloc(30000000);
int in()
{
    int ret=0;
    while ((*ch<'0'||*ch>'9')&&*ch!='-')
        ++ch;
    while (*ch>='0'&&*ch<='9')
        ret=ret*10+(*ch)-'0',++ch;
    return ret;
}
struct ask{
    int s,mo,di,id;
    bool operator < (const ask &n1) const
    {
        return mo<n1.mo;
    }
}a[1000010];
struct data{
    int val,id;
    bool operator < (const data &n1) const
    {
        return val<n1.val;
    }
}seq[110];

int n,m,q,u,v,w;
int dis[110][110],hh[110][110];
int ans[1000010];

void init()
{
    n=in(),m=in(),q=in();
    for (int i=1;i<=n;i++)
        seq[i].val=in(),seq[i].id=i;
    sort(seq+1,seq+n+1);
    memset(dis,0x3f,sizeof(dis));
    memset(hh,0x3f,sizeof(hh));
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i!=j)
                dis[i][j]=int(1e9)+1,hh[i][j]=int(1e9)+1;
    for (int i=1;i<=m;i++)
    {
        u=in(),v=in(),w=in();
        if (u!=v)
            dis[u][v]=dis[v][u]=min(dis[u][v],w);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            hh[i][j]=dis[i][j];
        sort(hh[i]+1,hh[i]+n+1);
    }
    for (int i=1;i<=q;i++)
        a[i].s=in(),a[i].mo=in(),a[i].di=in(),a[i].id=i;
    sort(a+1,a+q+1);
}
void updata(int x)
{
    for (int i=1;i<=n;i++)
        if (x!=i)
            for (int j=1;j<=n;j++)
                if (x!=j&&i!=j)
                    dis[i][j]=min(dis[i][j],dis[i][x]+dis[x][j]);
}
void work()
{
    int now=1;
    for (int i=1;i<=q;i++)
    {        
        while (now<=n&&a[i].mo>=seq[now].val)
        {
            updata(seq[now++].id);
            for (int i=1;i<=n;i++)
            {
                for (int j=1;j<=n;j++)
                    hh[i][j]=dis[i][j];
                sort(hh[i]+1,hh[i]+n+1);
            }
        }
        ans[a[i].id]=upper_bound(hh[a[i].s]+1,hh[a[i].s]+n+1,a[i].di)-hh[a[i].s]-1;
    }
    for (int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
}

int main()
{
    freopen("snackstore.in","r",stdin);
    freopen("snackstore.out","w",stdout);
    fread(ch,1,30000000,stdin);
    init();
    work();
    return 0;
}