Codeforces 730C. Bulmart

正文索引 [隐藏]

翻译
题解
代码

传送门：http://codeforces.com/problemset/problem/730/C

翻译

N个点M条边，每条边长度相等，度过时间为1。有K个点有价格不同数量不同的同一物品存货，假设物流不要费用，问在购买话费不超过LM时，最快能在何时买到。

题解

如果知道天数，我们可以用贪心很快的得出是否能用不超过给定话费完成调度。
所以我们二分天数。

代码

//while(true) RP++;
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
const int Maxn=5000;
int n,m,w,q;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int v0,int n0){
        v=v0;
        nxt=n0;
    }
};
Edge e[Maxn*Maxn+5];
int head[Maxn+5];
int nume;
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
    e[++nume]=Edge(u,head[v]);
    head[v]=nume;
}
struct Goods{
    int index;
    long long price;
    long long quality;
};
Goods gd[Maxn+5];
inline bool cmpGD(Goods a,Goods b){
    if (a.price<b.price) return true;
    return false;
}
int dist[Maxn+5];
queue<int> que;
inline void bfs(int x){
    memset(dist,-1,sizeof(dist));
    while(!que.empty()) que.pop();
    que.push(x);
    dist[x]=0;
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for (int i=head[now];i;i=e[i].nxt){
            int v=e[i].v;
            if (dist[v]==-1){
                dist[v]=dist[now]+1;
                que.push(v);
            }
        }
    }
}
inline bool check(int tim,long long req,long long lmt){
    long long rat=0;
    for (int i=1;i<=w;i++){
        if (req<=0) break;
        if (dist[gd[i].index]!=-1 && dist[gd[i].index]<=tim){
            long long tmp=min(req,gd[i].quality);
            req-=tmp;
            rat+=tmp*gd[i].price;
        }
        if (rat>lmt) break;
    }
    if (req<=0 && rat<=lmt) return true; else return false;
}
inline int query(int pos,long long req,long long lmt){
    bfs(pos);
    int left=0,right=n,Ans=n+1;
    while(left<=right){
        int mid=(left+right)/2;
        if (check(mid,req,lmt)){
            Ans=min(Ans,mid);
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    if (Ans==n+1) return -1; else return Ans;
}
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addEdge(x,y);
    }
    scanf("%d",&w);
    for (int i=1;i<=w;i++) scanf("%d%I64d%I64d",&gd[i].index,&gd[i].quality,&gd[i].price);
    sort(gd+1,gd+w+1,cmpGD);
    scanf("%d",&q);
    for (int i=1;i<=q;i++){
        int pos;
        long long req,lmt;
        scanf("%d%I64d%I64d",&pos,&req,&lmt);
        printf("%d\n",query(pos,req,lmt));
    }
    return 0;
}

100

101

102

//while(true) RP++;

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#include<iostream>

using namespace std;

const int Maxn=5000;

int n,m,w,q;

struct Edge{

int v,nxt;

Edge(){}

Edge(int v0,int n0){

v=v0;

nxt=n0;

}

};

Edge e[Maxn*Maxn+5];

int head[Maxn+5];

int nume;

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

e[++nume]=Edge(u,head[v]);

head[v]=nume;

}

struct Goods{

int index;

long long price;

long long quality;

};

Goods gd[Maxn+5];

inline bool cmpGD(Goods a,Goods b){

if (a.price<b.price) return true;

return false;

}

int dist[Maxn+5];

queue<int> que;

inline void bfs(int x){

memset(dist,-1,sizeof(dist));

while(!que.empty()) que.pop();

que.push(x);

dist[x]=0;

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=head[now];i;i=e[i].nxt){

int v=e[i].v;

if (dist[v]==-1){

dist[v]=dist[now]+1;

que.push(v);

}

inline bool check(int tim,long long req,long long lmt){

long long rat=0;

for (int i=1;i<=w;i++){

if (req<=0) break;

if (dist[gd[i].index]!=-1 && dist[gd[i].index]<=tim){

long long tmp=min(req,gd[i].quality);

req-=tmp;

rat+=tmp*gd[i].price;

}

if (rat>lmt) break;

}

if (req<=0 && rat<=lmt) return true; else return false;

}

inline int query(int pos,long long req,long long lmt){

bfs(pos);

int left=0,right=n,Ans=n+1;

while(left<=right){

int mid=(left+right)/2;

if (check(mid,req,lmt)){

Ans=min(Ans,mid);

right=mid-1;

}else{

left=mid+1;

}

if (Ans==n+1) return -1; else return Ans;

}

int main(){

//freopen("in.txt","r",stdin);

scanf("%d%d",&n,&m);

for (int i=1;i<=m;i++){

int x,y;

scanf("%d%d",&x,&y);

addEdge(x,y);

}

scanf("%d",&w);

for (int i=1;i<=w;i++) scanf("%d%I64d%I64d",&gd[i].index,&gd[i].quality,&gd[i].price);

sort(gd+1,gd+w+1,cmpGD);

scanf("%d",&q);

for (int i=1;i<=q;i++){

int pos;

long long req,lmt;

scanf("%d%I64d%I64d",&pos,&req,&lmt);

printf("%d\n",query(pos,req,lmt));

}

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑

Codeforces 730C. Bulmart

翻译

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

Codeforces 730C. Bulmart

翻译

题解

代码

扫一扫支付

评论 放弃治疗

评论放弃治疗