/* cogs 2507 零食店 跪了这题的数据了.... 第一遍Q*m 暴力询问 嗯 以为能的70 但只有40 Q已经到了1e6了 考试的时候 放弃了第三题又打了一遍 这次是Q*(n+logn) 最后发现和暴力分一样.... 好吧数据很厉害 吓得我在地上爬23333 好吧 考完了之后 看了正解 我靠这不和我的一个样吗 哎 啊啊啊 二分.... 傻傻的我笑了 都想出了方程 没打二分 ..... 迅速的改成二分 由迅速的wa了 23333 其实这样过不了了 Dij预处理会超时. 看了正解 直接Floyed 巧妙利用了floyed k层循环的含义 状态差不多 最后终于70了 然后优化常树 然后抄了个inf 1e9 这个inf大一点小一点都不对.... 知道最后也是卡过去的 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 110 #define inf 1e9+1 using namespace std; int n,m,Q,r[maxn],f[maxn][maxn][maxn]; int init(){ int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } struct node{ int c,o; }p[maxn]; int cmp(const node &x,const node &y){ return x.c<y.c; } void Floyed(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[k][i][j]=min(f[k-1][i][j],f[k-1][i][p[k].o]+f[k-1][p[k].o][j]); for(int i=0;i<=n;i++) for(int j=1;j<=n;j++) sort(f[i][j]+1,f[i][j]+1+n); } int main() { freopen("snackstore.in","r",stdin); freopen("snackstore.out","w",stdout); scanf("%d%d%d",&n,&m,&Q); int u,v,pos,t; for(int i=1;i<=n;i++){ p[i].c=init();p[i].o=i; r[i]=p[i].c; } sort(p+1,p+1+n,cmp);sort(r+1,r+1+n); for(int k=0;k<=n+1;k++) for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) f[k][i][j]=inf; for(int i=1;i<=m;i++){ u=init();v=init();t=init(); if(t<f[0][u][v]) f[0][u][v]=f[0][v][u]=t; } for(int i=1;i<=n;i++)f[0][i][i]=0; Floyed(); while(Q--){ u=init();v=init();t=init(); v=upper_bound(r+1,r+1+n,v)-r-1; pos=upper_bound(f[v][u]+1,f[v][u]+1+n,t)-f[v][u]-1; printf("%d ",pos-1); } return 0; } /*Dij预处理+二分找*/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<vector> #define pa pair<int,int> #define mk make_pair #define maxn 110 #define maxm 10010 #define inf 1e9+1 using namespace std; int n,m,Q,num,head[maxn],c[maxn],r[maxn],sum; int dis[maxn],f[maxn][maxn][maxn]; bool vis[maxn]; struct node{ int v,t,pre; }e[maxm*2]; priority_queue<pa,vector<pa>,greater<pa> >q; int init(){ int x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void Add(int from,int to,int dis){ num++;e[num].v=to; e[num].t=dis; e[num].pre=head[from]; head[from]=num; } void Dij(int s,int mx){ while(!q.empty())q.pop(); for(int i=0;i<=n;i++)dis[i]=inf; memset(vis,0,sizeof(vis)); q.push(mk(0,s));dis[s]=0; while(!q.empty()){ int k=q.top().second;q.pop(); if(vis[k]||(c[k]>mx&&k!=s))continue;vis[k]=1; for(int i=head[k];i;i=e[i].pre){ int v=e[i].v; if(dis[v]>dis[k]+e[i].t){ dis[v]=dis[k]+e[i].t; q.push(mk(dis[v],v)); } } } for(int i=1;i<=n;i++) f[s][mx][i]=dis[i]; sort(f[s][mx]+1,f[s][mx]+1+n); } void Solve(){ for(int i=1;i<=n;i++) for(int j=1;j<=sum;j++) Dij(i,j); } int main() { freopen("snackstore.in","r",stdin); freopen("snackstore.out","w",stdout); n=init();m=init();Q=init(); int u,v,t; for(int i=1;i<=n;i++){ c[i]=init();r[++sum]=c[i]; } sort(r+1,r+1+sum); sum=unique(r+1,r+1+sum)-r-1; for(int i=1;i<=n;i++){ int pos=lower_bound(r+1,r+1+sum,c[i])-r; c[i]=pos; } for(int i=1;i<=m;i++){ u=init();v=init();t=init(); Add(u,v,t);Add(v,u,t); } for(int k=0;k<=n+1;k++) for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) f[k][i][j]=inf; Solve(); while(Q--){ int pos=0; u=init();v=init();t=init(); v=upper_bound(r+1,r+1+sum,v)-r-1; pos=upper_bound(f[u][v]+1,f[u][v]+1+n,t)-f[u][v]-1; printf("%d ",pos); } return 0; } /*SPFA暴力找*/ #include<iostream> #include<cstdio> #include<cstring> #define maxn 110 #define maxm 10010 #define ll long long #define inf 0x3f3f3f3f using namespace std; ll n,m,Q,num,hea[maxn],dis[maxn],q[maxm*5],head,tail,c[maxn]; bool f[maxn]; struct node{ ll v,t,pre; }e[maxm*2]; ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void Add(ll from,ll to,ll dis){ num++;e[num].v=to; e[num].t=dis; e[num].pre=hea[from]; hea[from]=num; } void SPFA(ll s,ll mx,ll mxx){ for(int i=1;i<=n;i++)dis[i]=inf; for(int i=1;i<=n;i++)f[i]=0; head=1;tail=0;dis[s]=0; q[++tail]=s;f[s]=1; while(head<=tail){ ll k=q[head++];f[k]=0; if(c[k]>mx&&k!=s)continue; for(int i=hea[k];i;i=e[i].pre){ ll v=e[i].v; if(dis[v]>dis[k]+e[i].t){ dis[v]=dis[k]+e[i].t; if(f[v]==0&&dis[v]<=mxx){ f[v]=1;q[++tail]=v; } } } } } int main() { freopen("snackstore.in","r",stdin); //freopen("snackstore.out","w",stdout); n=init();m=init();Q=init(); ll u,v,t; for(int i=1;i<=n;i++) c[i]=init(); for(int i=1;i<=m;i++){ u=init();v=init();t=init(); Add(u,v,t);Add(v,u,t); } while(Q--){ int cnt=0; u=init();v=init(); t=init();SPFA(u,v,t); for(int i=1;i<=n;i++) if(dis[i]<=t&&i!=u)cnt++; cout<<Q<<" "<<cnt<<endl; } return 0; }