网站 申请,做的网站乱码怎么搞,成都工商注册咨询电话,江苏手机响应式网站建设题干#xff1a;
高玩小Q不仅喜欢玩寻宝游戏#xff0c;还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有nn个城镇#xff0c;编号依次为11到nn。 这些城镇之间有mm条单向道路#xff0c;第ii 条单项道路包含四个参数ui,vi,ai,biui,vi,ai,bi#xff0c;表示一条…题干
高玩小Q不仅喜欢玩寻宝游戏还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有nn个城镇编号依次为11到nn。 这些城镇之间有mm条单向道路第ii 条单项道路包含四个参数ui,vi,ai,biui,vi,ai,bi表示一条从uiui号城镇出发在vivi号城镇结束的单向道路因为是单向道路这不意味着小Q可以从vivi沿着该道路走到uiui。小Q的初始等级levellevel为11每当试图经过一条道路时需要支付costlog2levelailevelcostlog2levelailevel点积分并且经过该道路后小Q的等级会提升aiai级到达levelailevelai级。但是每条道路都会在一定意义上歧视低消费玩家准确地说如果该次所需积分costbicostbi那么小Q不能经过该次道路也不能提升相应的等级。 注意本游戏中等级为正整数但是积分可以是任意实数。 小Q位于11号城镇等级为11现在为了做任务要到nn号城镇去。这将会是一次奢侈的旅行请写一个程序帮助小Q找到需要支付的总积分最少的一条路线或判断这是不可能的。
Input
第一行包含一个正整数T(1≤T≤30)T(1≤T≤30)表示测试数据的组数。 每组数据第一行包含两个整数n,m(2≤n≤100000,1≤m≤200000)n,m(2≤n≤100000,1≤m≤200000)表示城镇数和道路数。 接下来mm行每行四个整数ui,vi,ai,bi(1≤ui,vi≤n,ui≠vi,0≤ai≤109,0≤bi≤60)ui,vi,ai,bi(1≤ui,vi≤n,ui≠vi,0≤ai≤109,0≤bi≤60)分别表示每条单向道路。
Output
对于每组数据输出一行一个整数即最少所需的总积分的整数部分如4.99994.9999输出441.01.0输出11。若不存在合法路线请输出−1−1。
Sample Input
1
3 3
1 2 3 2
2 3 1 6
1 3 5 0
Sample Output
2
解题报告 具体的题目的分析 博客 。总之就是把公式化简一下即考虑从1号点开始到各个点的cost发现根本用不到level而是只跟ai有关所以只需要dis数组中是ai的和的最小值即可最后答案中在取个log2就是答案了。判断b的时候即是否能走这条线刚开始理解错了理解成了跟level有关但是其实没关系只跟ai有关而ai更开始也理解错了不是从起点到该点的level和而是这条边自带的权值总之还是没读好题。。而且判断b的时候的cost也是该边的cost而非从起点过来的cost通过公式化简指数函数的运算就很容易求出该边的cost和bi之间的关系来进行continue
刚开始还觉得不同路径走的时候level也不一样啊比如我都是走到5号点一个是2号比如这个点level是3过来的一个是4号点过来的可能这个点的level是2所以相当于有很多权值的限制啊但是比赛的时候就得反过来想啊这么麻烦的话怎么可能有ac的呢所以肯定有化简的方法比如从公式入手发现这个对数函数刚好可以都约掉中间项所以只和终点有关和路径无关。还是要多做题多总结啊给公式的题往往可以公式入手
AC代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int MAXN 100000 5;
const int MAXE 200000 5;int n,m;
int cnt;
int head[MAXN] ;
ll dis[MAXN];
bool vis[MAXN];
struct Edge {int to;ll a;ll b;int ne;
} e[MAXE];
struct Point {int pos;ll cost;Point(){}Point(int pos,ll cost):pos(pos),cost(cost){}bool operator(const Point b)const {return cost b.cost;}
};
void add(int u,int v,ll a,ll b) {e[cnt].to v;e[cnt].a a;e[cnt].b b;e[cnt].ne head[u];head[u] cnt;
}
void Dijkstra(int st) {priority_queuePoint pq;dis[st] 1;pq.push(Point(st,1));while(!pq.empty()) {Point cur pq.top();pq.pop();if(vis[cur.pos] 1) continue;vis[cur.pos] 1;for(int i head[cur.pos]; i!-1; ie[i].ne) {if(1 e[i].a/cur.cost pow(2,e[i].b)) continue;//这里的pow其实可以找个数组预处理一下 if(dis[cur.pos] e[i].a dis[e[i].to] ) {dis[e[i].to] cur.cost e[i].a;//把dis[cur.pos]换成cur.cost行吗 pq.push(Point(e[i].to,dis[e[i].to])); }}} }
int main()
{int t;cint;//顶点1~nint u,v;ll a,b;while(t--) {cnt 0;memset(vis,0,sizeof(vis));memset(head,-1,sizeof(head));//别想当然写0scanf(%d%d,n,m); for(int i 1; in; i) dis[i] LLONG_MAX;//别把这一步放在读入n、m前面。。。 while(m--) {scanf(%d%d%lld%lld,u,v,a,b);add(u,v,a,b);}Dijkstra(1);
// printf(%lld\n\n\n,dis[n]); printf(%.0f\n,dis[n] LLONG_MAX ? -1 : floor(log2(dis[n])));}return 0 ;
}
总结 别把初始化放在读入m、n前面。。
Dijkstra 中//把dis[cur.pos]换成cur.cost行吗 是可以的但是还是写前者比较好因为Point结构体中这个变量其实就是储存一下为了排序的不是为了用的。。。
