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

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

题目链接：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&#p();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());
}