题目大意:一个无向图中每一条路有两个属性:体力和路径长.给出一个最大体力值k在满足不大于最大体力值的情况下求一条最短路径. 数据范围:n（<=5000） m（<=40000） 分析:以体力值跑一边最短路,因为m+n只有45000,所以考虑搜索每一条从s->t的路径. 并进行剪枝: {可行性剪枝:若此时消耗的体力值+下一条路消耗的体力值>最大体力值 最优化剪枝:若此时走过的路径长>=ans } code
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<cstdlib>#include<queue>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fod(i,a,b) for(int i=a;i>=b;i--)using namespace std;const int MAXN=5e3+10;const int MAXM=4e5+10;const int INF=0x3f3f3f;int last[MAXN],len=0,n,m,dis[MAXN],k,s,t;int ans=INF;bool vis[MAXN];struct edge{ int to,val,next,blood; edge(int to=0,int val=0,int next=0,int blood=0):to(to),val(val),next(next),blood(blood){}}e[MAXM*2];void add(int from,int to,int val,int blood){ e[++len]=edge(to,val,last[from],blood); last[from]=len;}void Spfa(int s){ fo(i,1,n) dis[i]=INF; memset(vis,0,sizeof(vis)); dis[s]=0; deque<int>q; q.push_front(s); vis[s]=1; while(!q.empty()){ int cur=q.front(); q.pop_front(); vis[cur]=0; for(int i=last[cur];i;i=e[i].next){ int id=e[i].to; if(dis[id]>dis[cur]+e[i].blood){ dis[id]=dis[cur]+e[i].blood; if(!vis[id]){ vis[id]=1; if(q.empty()){ q.push_front(id); } else{ if(dis[id]<dis[q.front()]) q.push_front(id); else q.push_back(id); } } } } }}void dfs(int cur,int dist,int blood){ if(cur==t) {ans=dist;return ;} for(int i=last[cur];i;i=e[i].next){ int id=e[i].to; if(dist+e[i].val>=ans||dis[id]+e[i].blood>blood) continue; vis[id]=1; dfs(id,dist+e[i].val,blood-e[i].blood); vis[id]=0; }}int main(){ scanf("%d%d",&n,&m); int x,y,c,d; fo(i,1,m){ scanf("%d%d%d%d",&x,&y,&c,&d); add(x,y,d,c); add(y,x,d,c); } scanf("%d%d",&s,&t); Spfa(t); memset(vis,0,sizeof(vis)); scanf("%d",&k); if(dis[s]>k) PRintf("-1"); else{ vis[s]=1; dfs(s,0,k); vis[s]=0; printf("%d",ans); } return 0;}新闻热点
疑难解答
