Problem Description
高玩小Q不仅喜欢玩寻宝游戏，还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有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找到需要支付的总积分最少的一条路线，或判断这是不可能的。
Input
第一行包含一个正整数T(1≤T≤30) ，表示测试数据的组数。 每组数据第一行包含两个整数n,m(2≤n≤100000,1≤m≤200000) ，表示城镇数和道路数。 接下来m 行，每行四个整数ui,vi,ai,bi(1≤ui,vi≤n,ui≠vi,0≤ai≤109,0≤bi≤60) ，分别表示每条单向道路。
Output
对于每组数据，输出一行一个整数，即最少所需的总积分的整数部分，如：4.9999 输出4 ，1.0 输出1 。若不存在合法路线请输出−1 。
Sample Input
1 3 3 1 2 3 2 2 3 1 6 1 3 5 0
Sample Output
2
由于今年还有女生赛，然后就去看了看我们去年打的女生赛的题，正好在写最短路，然后想到去年这个时候我们什么算法都不会，只会不用算法的签到题，幸运苟了一个铜末，今年再来看题目觉得自己稍微有一点点长进。这题我也就改了十几遍吧，怎么都找不到bug，然后无奈之下找了别人的代码来对拍，发现我少了个初始化。嗯我是zz。
这题就是一个很简单的dijkstra最短路堆优化，然后利用题目信息将数据进行化简，发现其实就是一道最短路题再把最终结果取个log2就好了。
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <cmath> using namespace std; const int MAXN=200005; const long long INF=1ll << 60; int n, m; long long p[61]; struct qnode{ int v; long long a; int b; qnode(int _v=0,long long _a = 0):v(_v),a(_a){} bool operator <(const qnode &r)const{ return a > r.a; } }; struct Edge{ int v; long long a; int b; Edge(int _v=0,long long _a=0, int _b = 0):v(_v),a(_a),b(_b){} }; vector<Edge>E[MAXN]; bool vis[MAXN]; long long dist[MAXN]; void Dijkstra(int n,int start){ memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) dist[i]=INF; priority_queue<qnode>que; while(!que.empty()) que.pop(); dist[start]=1; que.push(qnode(start,1)); qnode tmp; while(!que.empty()){ tmp=que.top(); que.pop(); int u=tmp.v; if(vis[u])continue; vis[u]=true; for(int i = 0; i < E[u].size(); i++){ int v = E[u][i].v; if(1 + E[u][i].a / dist[u] < p[E[u][i].b]) continue; if(dist[v] > dist[u] + E[u][i].a) { dist[v] = dist[u] + E[u][i].a; que.push(qnode(v,dist[v])); } } } } void addedge(int u,int v,long long w1, int w2){ E[u].push_back(Edge(v,w1, w2)); } int main() { //freopen("test2.in","w",stdout); p[0] = 1; for(int i = 1; i < 61; i++) p[i] = p[i-1] * 2; int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); for(int i = 0; i <= n; i++) E[i].clear(); for(int i = 0; i < m; i++) { int u, v; long long a1; int b1; scanf("%d%d%lld%d", &u, &v, &a1, &b1); addedge(u, v, a1, b1); } Dijkstra(n, 1); if(dist[n] == INF) printf("-1\n"); else printf("%.0f\n", floor(log2(dist[n]))); } return 0; }
