一道不算太难的最短路喵~
容我吐槽一下，酋长的地位居然不是最高的额——那你特么的居然还算是酋长？！
枚举一个地位区间 [i..i+M-1] 只要所有的交易者的地位都在该区间中，那么就不会引起冲突
而这个可悲的酋长是必须在区间中的，所以若酋长的地位为 L0 那么该枚举的区间就是 [L0-i, L0+M-i] {i|0<=i<=M}
然后就是裸的 dijkstra 了，取出地位在区间中的点，然后新增一个点 N+1，向所有点连边，距离是所有物品的直接价格
若 物品 i 可以通过 物品 j 来降价，那么从 j 向 i 连一条边，距离为降价后的价格
以 N+1 为源点跑一个最短路就可以了
我发现带内部调整的优先队列不是蛮好写的嘛~
#include <cstdio>
#include <cstring>
const int sizeOfPoint=;
const int sizeOfEdge=; int n;
int h[sizeOfPoint];
inline int getint();
inline void putint(int); struct edge {int point, dist; edge * next;};
edge memory[sizeOfEdge], * port=memory;
edge * e[sizeOfPoint];
inline edge * newedge(int point, int dist, edge * next)
{
edge * ret=port++;
ret->point=point; ret->dist=dist; ret->next=next;
return ret;
}
inline void link(int u, int v, int d)
{
e[u]=newedge(v, d, e[u]); e[v]=newedge(u, d, e[v]);
} struct priority_queue
{
int size, q[sizeOfPoint];
int id[sizeOfPoint];
inline int front() {return q[];}
inline bool exist(int x) {return id[x]>;}
inline void down(int i)
{
register int x=q[i];
register int j;
for (j=i<<;j<=size;i=j, j=i<<)
{
if (j<size && h[q[j+]]<h[q[j]]) j++;
if (h[q[j]]<h[x]) id[q[i]=q[j]]=i;
else break;
}
id[q[i]=x]=i;
}
inline void up(int i)
{
register int x=q[i];
register int j;
for (j=i>>;j;i=j, j=i>>)
if (h[q[j]]>h[x]) id[q[i]=q[j]]=i;
else break;
id[q[i]=x]=i;
}
inline void build(int _size)
{
size=_size;
for (int i=;i<=size;i++) id[q[i]=i]=i;
for (int i=size>>;i;i--) down(i);
}
inline void pop()
{
id[q[]]=;
id[q[]=q[size--]]=;
down();
}
inline void deskey(int x)
{
up(id[x]);
}
}; inline int min(int x, int y) {return x<y?x:y;}
inline int max(int x, int y) {return x>y?x:y;}
inline void dijkstra(); int main()
{
n=getint();
for (int i=;i<=n;i++)
for (int j=;j<i;j++)
{
int A=getint();
if (A>=) link(i, j, A);
}
memset(h, 0x3F, sizeof h); h[]=;
dijkstra(); int ans=;
for (int i=;i<=n;i++) ans=max(ans, h[i]); putint(ans); return ;
}
inline int getint()
{
register int num=;
register char ch=;
do ch=getchar(); while ((ch<'' || ch>'') && ch!='x');
if (ch=='x') return -;
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline void putint(int num)
{
char stack[];
register int top=;
if (num==) stack[top=]='';
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
putchar('\n');
}
inline void dijkstra()
{
priority_queue q;
q.build(n);
for ( ;q.size; )
{
int u=q.front(); q.pop();
for (edge * i=e[u];i;i=i->next) if (q.exist(i->point) && h[i->point]>h[u]+i->dist)
{
h[i->point]=h[u]+i->dist;
q.deskey(i->point);
}
}
}
本傻装B系列