http://www.cogs.pro/cogs/problem/problem.php?pid=2507

時間限制：1 s?? 內存限制：256 MB

【題目描述】

? ?

? ?成功找到了學長之后學姐感覺到有些餓，于是決定去附近的零食店給自己和學長買些零食。

? ?焦作市的有n家零食店，由m條道路連接著這些零食店，每條道路都有自己的長度l，每家零食店都有自己的消費指數。

? ?由于學姐是個窮B，所以去買零食的路上不能經過某些消費指數超過一定限度的店。

? ?同時由于學姐體力有限，所以去買零食的過程中走的路程不能太長。

? ?想來想去學姐決定去問學長買什么零食比較好，反正到最后都是學長吃╮(╯_╰)╭

? ?在去問之前，學姐準備先做好準備，她把焦作市（所有零食店）的地圖給了你，希望你能編出一個程序快速回答她從某個零食店出發，在上述限制下有多少家零食店可供她挑選。

?

?

【輸入格式】

?

? ?第一行三個正整數n，m，q，分別代表零食店數，道路數和詢問數。

? ?接下來一行n個正整數，第i個正整數vi代表第i家零食店的消費指數。

? ?接下來m行，第i行三個正整數x,y,l,代表第i條道路連接編號為x和y的兩個零食店，長度為l。

? ?接下來q行第i行三個正整數s,c,d，代表第i個詢問要求從s出發，所經過的零食店的消費指數不能超過c（除了起點和終點以外），且行走路程不超過d。

?

?

【輸出格式】

? ?一共q行，第i行一個整數代表在第i個詢問的要求下有多少家零食店可供學姐挑選。

【樣例輸入】

5 5 2 1 2 3 4 5 1 2 1 1 3 4 2 3 2 1 4 3 2 5 1 1 1 3 2 1 2

【樣例輸出】

2 3

【提示】

?

樣例中第一個詢問能去編號為2/4的零食店。

第二個詢問能去編號為1/3/5的零食店。

對于40%的數據，n≤10，m≤20，q=1。

對于70%的數據，m≤500，q≤10000。

對于100%的數據，n≤100，m≤10000，q≤1000000，vi,c,d≤10^9，1≤x,y,s≤n，l≤10^6。

?

利用floyd 第一重循環k，所有中間點的編號都小于k

本體對消費指數的限制恰好是中間點

所以講點按消費指數由小到大排序

f[k][i][j] 從i到j，中間經過的點的消費指數<=k的消費指數的最短路

當消費指數限制為v時，二分找到第一個消費指數<=v的點a，

從點u出發，就是在f[a][u][]里找最短路<=某個數的點的個數

排序之后二分即可

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int f[101][101][101],dy[101],a[101]; struct node {int cost,id; }e[101]; void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } bool cmp(node p,node q) {return p.cost<q.cost; } int main() {freopen("snackstore.in","r",stdin);freopen("snackstore.out","w",stdout);int n,m,q;read(n); read(m); read(q);for(int i=1;i<=n;i++) read(a[i]),e[i].cost=a[i],e[i].id=i;sort(a+1,a+n+1);sort(e+1,e+n+1,cmp);for(int i=1;i<=n;i++) dy[e[i].id]=i;int u,v,w;for(int k=0;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[k][i][j]=1e9+1;while(m--){scanf("%d%d%d",&u,&v,&w);u=dy[u]; v=dy[v];f[0][u][v]=f[0][v][u]=min(w,f[0][u][v]);}for(int i=0;i<=n;i++)for(int j=1;j<=n;j++)f[i][j][j]=0;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][k]+f[k-1][k][j]);for(int i=0;i<=n;i++)for(int j=1;j<=n;j++)sort(f[i][j]+1,f[i][j]+n+1);while(q--){scanf("%d%d%d",&u,&v,&w);v=upper_bound(a+1,a+n+1,v)-a-1;u=dy[u];w=upper_bound(f[v][u]+1,f[v][u]+n+1,w)-f[v][u]-1;printf("%d\n",w-1);} }

?

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/7395897.html

總結

以上是生活随笔為你收集整理的COGS 2507 零食店的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。