admin 管理员组

文章数量: 887021

【HDU

题目链接：.php?pid=6290

题目看起来有些有些复杂，但是理解起来并不是很困难，主要是在数据的处理上需要上心，因为数据wa了好多次   =  =。

解题思路：就算dijkstra模板，在这个基础上增加一些判断和处理，比如cost=log2（（level+ai）/level）和cost<bi
，在基础模板上增加判断就可以

ac代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
#include<cmath>
#define maxn 1000005
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,cnt;
ll dis[maxn];
int mark[maxn];
int head[maxn];
struct node
{int u;int v;ll a;ll b;int next;
}nod[maxn];
struct Node
{int pos;ll  cost;
//	node(){}//没有此构造函数不能写  node t  这样
//	node(int pos,int cost):pos(pos),cost(cost){}//可以写node(pos,cost)这样friend bool operator < (Node a,Node b)//运算符重载<   先把格式记住{return a.cost> b.cost;}
};void add(int u,int v,ll a,ll b)//加边
{nod[cnt].u=u;nod[cnt].v=v;nod[cnt].a=a;nod[cnt].b=b;nod[cnt].next=head[u];head[u]=cnt++;
}void init()
{memset(head,-1,sizeof(head));memset(mark,0,sizeof(mark));memset(dis,inf,sizeof(dis));cnt=0;
}
void dijkstra()
{Node tmp,qq;tmp.pos=1;tmp.cost=1;priority_queue<Node> q;dis[1]=1;q.push(tmp);while(q.size()){tmp=q.top();q.pop();int u=tmp.pos;if(mark[u]) continue;mark[u]=1;for(int i=head[u];i!=-1;i=nod[i].next){int v=nod[i].v;ll cos=nod[i].a;if((ll)cos/dis[u]<nod[i].b)continue;if(dis[v]>dis[u]+cos){dis[v]=dis[u]+cos;qq.pos=v;qq.cost=dis[v];q.push(qq);}}		}if(dis[n]==inf)  printf("-1\n");else printf("%lld\n",(ll)(log2(dis[n]*1.0)));
}int main()
{int t;scanf("%d",&t);while(t--){init();scanf("%d%d",&n,&m);int u,v;ll a,b;for(int i=0;i<m;i++){scanf("%d%d%lld%lld",&u,&v,&a,&b);add(u,v,a,((ll)1<<b)-1);}dijkstra();}return 0;
}

需要注意的是，在进行对数据处理的时候，为了方便就将node结构体中存放的是2^cost-1  对之后的判断和操作进行了简化，但最后输出的时候还是需要将其转换回来，所以就会涉及到精度问题，题目要求了就是下取整，比较方便。

总结一句就是自己的dijkstra的邻接表的使用还是超级水，靠着模板都会出一大堆错误。= = ，可怕可怕

本文标签： HDU

版权声明：本文标题：【HDU 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1720340349h719854.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。