题目链接：点击打开链接
题目大意：略。
解题思路：这是一个最短路的问题，初始等级为1，所以总积分的计算可以用对数化简成 log( (1+a1)/1 * (1+a1+a2)/(1+a1)...) => log(1+a1+a2+....an)。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=100000+500,maxm=200000+500; int n,m,ecnt; ll vis[maxn], dis[maxn], head[maxn]; struct edge{ int u,v,a,b,next; }es[maxm]; struct node{ int id; ll dis; node(int id,ll dis):id(id),dis(dis){} bool operator < (const node &nd)const{ return dis>nd.dis; } }; void init() { ecnt=0; mem(vis,0); mem(dis,INF); mem(head,-1); } void insertEdge(int u,int v,int a,int b) { es[ecnt].u=u; es[ecnt].v=v; es[ecnt].a=a; es[ecnt].b=b; // 从某个顶点出发一共有多少条边，边静态链接 es[ecnt].next=head[u]; head[u]=ecnt++; } int dijkstra(int s,int t) { priority_queue<node> que; que.push(node(s,1)); dis[s]=1; while(!que.empty()) { node tp=que.top(); que.pop(); int tpid=tp.id; if(tpid==t) { for(int i=0;;i++) if((1LL<<i)>tp.dis) return i-1; } if(vis[tpid]) continue; vis[tpid]=1; for(int i=head[tpid]; i!=-1; i=es[i].next) { if(vis[es[i].v]) continue; // 这里整数除不影响结果，因为跟它比较的也是整数，所以小数部分可以不用考虑 if((es[i].a+tp.dis)/tp.dis >= (1LL<<es[i].b) && es[i].a+tp.dis<dis[es[i].v]) { dis[es[i].v]=es[i].a+tp.dis; que.push(node(es[i].v,dis[es[i].v])); } } } return -1; } int main() { int T; scanf("%d",&T); while(T-- && ~scanf("%d%d",&n,&m)) { init(); int u,v,a,b; for(int i=0;i<m;i++) { scanf("%d%d%d%d",&u,&v,&a,&b); insertEdge(u,v,a,b); } printf("%d\n",dijkstra(1,n)); } return 0; }
