首页 > 代码库 > [poj 1502]昂贵的聘礼
[poj 1502]昂贵的聘礼
一道不算太难的最短路喵~
容我吐槽一下，酋长的地位居然不是最高的额——那你特么的居然还算是酋长？！
枚举一个地位区间 [i..i+M-1] 只要所有的交易者的地位都在该区间中，那么就不会引起冲突
而这个可悲的酋长是必须在区间中的，所以若酋长的地位为 L0 那么该枚举的区间就是 [L0-i, L0+M-i] {i|0<=i<=M}
然后就是裸的 dijkstra 了，取出地位在区间中的点，然后新增一个点 N+1，向所有点连边，距离是所有物品的直接价格
若 物品 i 可以通过 物品 j 来降价，那么从 j 向 i 连一条边，距离为降价后的价格
以 N+1 为源点跑一个最短路就可以了
我发现带内部调整的优先队列不是蛮好写的嘛~
1 #include <cstdio> 2 #include <cstring> 3 const int sizeOfPoint=128; 4 const int sizeOfEdge=32768; 5 6 int n; 7 int h[sizeOfPoint]; 8 inline int getint(); 9 inline void putint(int); 10 11 struct edge {int point, dist; edge * next;}; 12 edge memory[sizeOfEdge], * port=memory; 13 edge * e[sizeOfPoint]; 14 inline edge * newedge(int point, int dist, edge * next) 15 { 16 edge * ret=port++; 17 ret->point=point; ret->dist=dist; ret->next=next; 18 return ret; 19 } 20 inline void link(int u, int v, int d) 21 { 22 e[u]=newedge(v, d, e[u]); e[v]=newedge(u, d, e[v]); 23 } 24 25 struct priority_queue 26 { 27 int size, q[sizeOfPoint]; 28 int id[sizeOfPoint]; 29 inline int front() {return q[1];} 30 inline bool exist(int x) {return id[x]>0;} 31 inline void down(int i) 32 { 33 register int x=q[i]; 34 register int j; 35 for (j=i<<1;j<=size;i=j, j=i<<1) 36 { 37 if (j<size && h[q[j+1]]<h[q[j]]) j++; 38 if (h[q[j]]<h[x]) id[q[i]=q[j]]=i; 39 else break; 40 } 41 id[q[i]=x]=i; 42 } 43 inline void up(int i) 44 { 45 register int x=q[i]; 46 register int j; 47 for (j=i>>1;j;i=j, j=i>>1) 48 if (h[q[j]]>h[x]) id[q[i]=q[j]]=i; 49 else break; 50 id[q[i]=x]=i; 51 } 52 inline void build(int _size) 53 { 54 size=_size; 55 for (int i=1;i<=size;i++) id[q[i]=i]=i; 56 for (int i=size>>1;i;i--) down(i); 57 } 58 inline void pop() 59 { 60 id[q[1]]=0; 61 id[q[1]=q[size--]]=1; 62 down(1); 63 } 64 inline void deskey(int x) 65 { 66 up(id[x]); 67 } 68 }; 69 70 inline int min(int x, int y) {return x<y?x:y;} 71 inline int max(int x, int y) {return x>y?x:y;} 72 inline void dijkstra(); 73 74 75 int main() 76 { 77 n=getint(); 78 for (int i=2;i<=n;i++) 79 for (int j=1;j<i;j++) 80 { 81 int A=getint(); 82 if (A>=0) link(i, j, A); 83 } 84 memset(h, 0x3F, sizeof h); h[1]=0; 85 dijkstra(); 86 87 int ans=0; 88 for (int i=1;i<=n;i++) ans=max(ans, h[i]); 89 90 putint(ans); 91 92 return 0; 93 } 94 inline int getint() 95 { 96 register int num=0; 97 register char ch=0; 98 do ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘x‘); 99 if (ch==‘x‘) return -1;100 do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);101 return num;102 }103 inline void putint(int num)104 {105 char stack[15];106 register int top=0;107 if (num==0) stack[top=1]=‘0‘;108 for ( ;num;num/=10) stack[++top]=num%10+‘0‘;109 for ( ;top;top--) putchar(stack[top]);110 putchar(‘\n‘);111 }112 inline void dijkstra()113 {114 priority_queue q;115 q.build(n);116 for ( ;q.size; )117 {118 int u=q.front(); q.pop();119 for (edge * i=e[u];i;i=i->next) if (q.exist(i->point) && h[i->point]>h[u]+i->dist)120 {121 h[i->point]=h[u]+i->dist;122 q.deskey(i->point);123 }124 }125 }
[poj 1502]昂贵的聘礼
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。