最短路floyd算法_奥本海姆信号与系统第二版答案
奢侈的旅行
Time Limit: 14000/7000 MS (Java/Others) Memory Limit: / K (Java/Others)
Total Submission(s): 561 Accepted Submission(s): 109
n个城镇，编号依次为
1到
n。
这些城镇之间有
m条单向道路，第
i 条单项道路包含四个参数
ui,vi,ai,bi，表示一条从
ui号城镇出发，在
vi号城镇结束的单向道路，因为是单向道路，这不意味着小Q可以从
vi沿着该道路走到
ui。小Q的初始等级
level为
1，每当试图经过一条道路时，需要支付
cost=log2level+ailevel点积分，并且经过该道路后，小Q的等级会提升
ai级，到达
level+ai级。但是每条道路都会在一定意义上歧视低消费玩家，准确地说，如果该次所需积分
cost<bi，那么小Q不能经过该次道路，也不能提升相应的等级。
注意：本游戏中等级为正整数，但是积分可以是任意实数。
小Q位于
1号城镇，等级为
1，现在为了做任务要到
n号城镇去。这将会是一次奢侈的旅行，请写一个程序帮助小Q找到需要支付的总积分最少的一条路线，或判断这是不可能的。
T(1≤T≤30)，表示测试数据的组数。
每组数据第一行包含两个整数
n,m(2≤n≤,1≤m≤)，表示城镇数和道路数。
接下来
m行，每行四个整数
ui,vi,ai,bi(1≤ui,vi≤n,ui≠vi,0≤ai≤109,0≤bi≤60)，分别表示每条单向道路。
4.9999输出
4，
1.0输出
1。若不存在合法路线请输出
−1。
题意：小Q在1想去n, 给你n个城市m条路径，然后是单向路径，a代表通过这条路小Q提升的等级，b代表经过这条路需要耗费最小的过路费。
log2[(a+level)/level]>=b，可以两边取log2 变成a/level+1>=2^b 转化成 a/level >=2^b-1;
也就发现花费跟2的次方-1有关，就开始建图，2^b-1提前处理好。
卡spfa，用dijkstra+堆优化，对于每个点需要判断a/level 和 2^b-1的关系，如果小于则不能通过，dis[u]存的是level
#include<bits/stdc++.h> using namespace std; const long long INF=1e18; long long dis[]; int head[]; int vis[]; struct node{ int u; int v; long long a; long long b; int next; }no[]; struct Node{ int pos; long long dis; friend bool operator<(const Node&a,const Node&b) { return a.dis>b.dis; } }; int cnt; int n,m; void add(int u,int v,long long a,long long b) { no[cnt].u=u; no[cnt].v=v; no[cnt].a=a; no[cnt].b=b; no[cnt].next=head[u]; head[u]=cnt++; } void dj() { for(int i=0;i<=n;i++) { vis[i]=0; dis[i]=INF; } priority_queue<Node>que; Node p,q; p.pos=1; p.dis=1ll; que.push(p); dis[1]=1ll; while(!que.empty()) { p=que.top(); que.pop(); int u=p.pos; if(vis[u]) continue; vis[u]=1; for(int i=head[u];i!=-1;i=no[i].next) { int v=no[i].v; long long cost=no[i].a; if((long long )cost/dis[u] < no[i].b)// continue; if(dis[v] > dis[u]+cost) { dis[v]=dis[u]+cost; q.pos=v; q.dis=dis[v]; que.push(q); } } } if(dis[n]==INF) printf("-1\n"); else printf("%d\n",(int)(log2(dis[n]*1.0))); } int main() { int t; scanf("%d",&t); while(t--) { cnt=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); int u,v; long long a,b; for(int i=0;i<m;i++) { scanf("%d%d%lld%lld",&u,&v,&a,&b); add(u,v,a,((long long)1<<b)-1); } dj(); } return 0; } 
