首页 > 代码库 > BZOJ 1975 魔法猪学院（K短路）

BZOJ 1975 魔法猪学院（K短路）

2024-07-09 00:10:05   225人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1975

题意：给出一个带权有向图。求一个最大的K使得前K短路的长度之和不大于给定的值Sum。

思路：首先，求出每个点到n的最短路。接着，使用优先队列，节点为(D，u)。首先将(dis[1],1)进队。由于D在任意时候为一条1到n的路径的长度，那么对于边<u,v,w>,D-dis[u]+w+dis[v]为一条新的路径的长度。

 

vector<pair<int,double> > g[N],g1[N];double dis[N];int n,m;double Sum;struct node{    int v;    double dis;        node(){}    node(int _v,double _dis)    {        v=_v;        dis=_dis;    }        int operator<(const node &a) const    {        return dis>a.dis;    }};int inq[N];void SPFA(){    int i;    FOR1(i,n) dis[i]=dinf;    dis[n]=0; inq[n]=1;    queue<int> Q;    Q.push(n);    int u,v;    double w;    while(!Q.empty())    {        u=Q.front();        Q.pop();                inq[u]=0;        FOR0(i,SZ(g1[u]))        {            v=g1[u][i].first;            w=g1[u][i].second;            if(dis[v]>dis[u]+w)            {                dis[v]=dis[u]+w;                if(!inq[v]) inq[v]=1,Q.push(v);            }        }    }}priority_queue<node> Q;int cal(){    Q.push(node(1,dis[1]));    int ans=0,i,v;    node p;    double w;    while(!Q.empty())    {        p=Q.top();        Q.pop();                if(p.dis>Sum+EPS) break;                if(p.v==n)         {            ans++;            Sum-=p.dis;            continue;        }        FOR0(i,SZ(g[p.v]))        {            v=g[p.v][i].first;            w=g[p.v][i].second;            Q.push(node(v,p.dis-dis[p.v]+w+dis[v]));        }    }    return ans;}int main(){    RD(n,m); RD(Sum);    int i,u,v;    double w;    FOR1(i,m)    {        RD(u,v);RD(w);        g[u].pb(MP(v,w));        g1[v].pb(MP(u,w));    }    SPFA();    PR(cal());}

 

 

 


联系
我们