记录编号	326656	评测结果	AAAAAAAWWT
题目名称	零食店	最终得分	70
用户昵称	KZNS	是否通过	未通过
代码语言	C++	运行时间	3.029 s
提交时间	2016-10-21 12:00:37	内存使用	4.27 MiB

//KZNS
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 105
#define INF 1000000005
int input() {
    int a = 0;
    char c = getchar();
    while (!('0' <= c && c <= '9'))
        c = getchar();
    while ('0' <= c && c <= '9') {
        a = a * 10 + c - '0';
        c = getchar();
    }
    return a;
}
int N, M, Q;
int V[Nmax];
int gp[Nmax][Nmax][Nmax];
int vls[Nmax];
int als[Nmax][Nmax] = {0};
inline bool cmp2(const int a, const int b) {
    return V[a] < V[b];
}
void init() {
    N = input();
    M = input();
    Q = input();
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            for (int k = 0; k <= N; k++)
                gp[k][i][j] = INF;
    for (int i = 1; i <= N; i++) {
        V[i] = input();
        vls[i] = i;
        gp[0][i][i] = 0;
    }
    int a, b, c;
    for (int i = 0; i < M; i++) {
        a = input();
        b = input();
        c = input();
        gp[0][a][b] = min(gp[0][a][b], c);
        gp[0][b][a] = min(gp[0][b][a], c);
    }
    sort(vls+1, vls+1+N, cmp2);
    int k;
    for (int u = 1; u <= N; u++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                gp[u][i][j] = min(gp[u-1][i][j], gp[u-1][i][vls[u]] + gp[u-1][vls[u]][j]);
    for (int u = 0; u <= N; u++)
        for (int i = 1; i <= N; i++)
            sort(gp[u][i]+1, gp[u][i]+1+N);
}
void work() {
    int f, c, d;
    int l, r, md;
    int ll, rr;
    for (int i = 0; i < Q; i++) {
        f = input();
        c = input();
        d = input();
        l = 0;
        r = N;
        while (r-l > 1) {
            md = l+r>>1;
            if (V[vls[md]] <= c)
                l = md;
            else
                r = md;
        }
        if (V[vls[r]] <= c)
            l = r;
        ll = 1;
        rr = N;
        while (rr - ll > 1) {
            md = ll+rr>>1;
            if (gp[l][f][md] <= d)
                ll = md;
            else
                rr = md;
        }
        if (gp[l][f][rr] <= d)
            ll = rr;
        printf("%d\n", ll - 1);
    }
}
int main() {
    freopen("snackstore.in", "r", stdin);
    freopen("snackstore.out", "w", stdout);
    init();
    work();
    return 0;
}
//UBWH