记录编号	326600	评测结果	AAAAAAATTT
题目名称	零食店	最终得分	70
用户昵称	ciyou	是否通过	未通过
代码语言	C++	运行时间	3.311 s
提交时间	2016-10-21 10:44:37	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct edge{
    int from,to,cost;
};
struct vertix{
    int dis,id;
    bool operator < (const vertix& c) const{
        return dis>c.dis;
    }
};
vector<edge> edges;
vector<int> G[101];
priority_queue<vertix> Q;
int dis[101],vis[101],C[101],is_choosen[101];
int n,m,q;
int dijkstra(int,int,int);
edge make_edge(int,int,int);
vertix make_vertix(int,int);
void add_edge(int,int,int);
int main(){
    freopen("snackstore.in","r",stdin);
    freopen("snackstore.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    edges.clear();
    for(int i=1;i<=n;i++) G[i].clear();
    for(int i=1;i<=n;i++) scanf("%d",&C[i]);
    for(int i=1;i<=m;i++){
        int x,y,l;
        scanf("%d%d%d",&x,&y,&l);
        add_edge(x,y,l);
    }
    for(int i=1;i<=q;i++){
        int s,c,d;
        scanf("%d%d%d",&s,&c,&d);
        printf("%d\n",dijkstra(s,c,d));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
edge make_edge(int u,int v,int w){
    edge temp;
    temp.from=u;
    temp.to=v;
    temp.cost=w;
    return temp;
}
vertix make_vertix(int id,int dis){
    vertix temp;
    temp.dis=dis;
    temp.id=id;
    return temp;
}
void add_edge(int u,int v,int w){
    if(v==u) return;
    //cout<<"PRE:"<<u<<"->"<<v<<"="<<w<<endl;

    for(int i=0;i<G[u].size();i++){
        edge e=edges[G[u][i]];
        if(e.to==v){
            //cout<<"From "<<u<<" to "<<e.to<<"="<<e.cost<<" New="<<w<<endl;
            if(e.cost>w){
                edges[G[u][i]].cost=w;
                for(int i=0;i<G[v].size();i++){
                    e=edges[G[v][i]];
                    if(e.to==u){
                        //cout<<"From "<<v<<" to "<<e.to<<"="<<e.cost<<" New="<<w<<endl;
                        edges[G[v][i]].cost=w;
                    }
                }
                return;
            }
        }
    }
    //cout<<"ADD:"<<u<<"->"<<v<<"="<<w<<endl;
    edges.push_back(make_edge(u,v,w));
    G[u].push_back(edges.size()-1);
    //cout<<"G["<<u<<"].size="<<G[u].size()<<endl;
    edges.push_back(make_edge(v,u,w));
    G[v].push_back(edges.size()-1);
    //cout<<"G["<<v<<"].size="<<G[v].size()<<endl;
    return;
}
int dijkstra(int s,int c,int d){
    //cout<<G[5].size()<<endl;

    int ans=0;
    memset(is_choosen,0,sizeof(is_choosen));
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    Q.push(make_vertix(s,0));
    while(!Q.empty()){
        int p=Q.top().id;
        Q.pop();
        if(vis[p]) continue;
        else vis[p]=1;
        for(int i=0;i<G[p].size();i++){
            edge e=edges[G[p][i]];
            //cout<<G[p].size()<<endl;
            if(dis[e.to]>dis[p]+e.cost){
                dis[e.to]=dis[p]+e.cost;
                //cout<<p<<"->"<<e.to<<"="<<dis[e.to]<<" while D="<<d<<" ";
                if(dis[e.to]<=d){
                    is_choosen[e.to]=1;
                    //cout<<" Done!";
                }
                //cout<<endl;
                if(dis[e.to]<=d&&C[e.to]<=c) Q.push(make_vertix(e.to,dis[e.to]));
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(is_choosen[i]) ans++;
    }
    return ans;
}