首页 > 代码库 > [vijos P1880]ファーラの力
[vijos P1880]ファーラの力
据说这是一道 JOI 的题？反正我觉着挺好的喵~
题目看起来十分可怕，但是代码还是很短的
显而易见的，ans 因分为3个部分：1.中途增加光压的时间 2.中途减少光压的时间 3. 所有路程的总时间
发现如果把每个柱子的光压下限0去掉后，光压无论在何时加都是一样的
因为若从某刻光压小于等于0后，我们可以按需调整光压，就不再出现人为降低光压这个操作，而不论如何最后的光压一定是 E[终点]
所以
1.光压无论在何时加都是一样的
而我们又发现在路径上减少1个光压和在光柱上人为调整1个光压的时间是一样的
光压差就是时间差
我们用dist[n]表示到点n时的光压
2.X-dist[终点]=中途减少光压的时间+所有路程的总时间
又由1得E[终点]-dist[终点]=中途增加光压的时间
这两个式子都是随着dist[终点]的递增而递减的
只要算出最大的dist[终点]即可，这就是为什么要用最短路稍的原因
ans=(X-dist[终点])+(E[终点]-dist[终点)=X+E[终点]-2*dist[终点]
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 typedef std::pair<long long, int> node; 5 const long long INF=0x7FFFFFFFFFFFFFLL; 6 const int sizeOfPoint=100001; 7 const int sizeOfEdge=600006; 8 9 struct edge {int point, dist; edge * next;};10 edge memory[sizeOfEdge], * port=memory;11 edge * e[sizeOfPoint];12 inline edge * newedge(int point, int dist, edge * next)13 {14 edge * ret=port++;15 ret->point=point; ret->dist=dist; ret->next=next;16 return ret;17 }18 19 int N, M, X;20 int E[sizeOfPoint];21 long long dist[sizeOfPoint];22 std::priority_queue<node> q;23 inline long long min(long long x, long long y) {return x<y?x:y;}24 inline int getint();25 inline void putint(long long);26 27 int main()28 {29 N=getint(), M=getint(), X=getint();30 for (int i=1;i<=N;i++) E[i]=getint();31 for (int i=0;i<M;i++)32 {33 int A, B, T;34 A=getint(), B=getint(), T=getint();35 if (E[A]>=T) e[A]=newedge(B, T, e[A]);36 if (E[B]>=T) e[B]=newedge(A, T, e[B]);37 }38 39 for (int i=1;i<=N;i++) dist[i]=-INF;40 for (q.push(node(X, 1));!q.empty(); )41 {42 node u=q.top(); q.pop();43 if (dist[u.second]!=-INF) continue;44 dist[u.second]=u.first;45 for (edge * i=e[u.second];i;i=i->next)46 q.push(node(min(u.first-i->dist, E[i->point]), i->point));47 }48 49 if (dist[N]==-INF) printf("-1\n");50 else putint(X+E[N]-(dist[N]<<1));51 52 return 0;53 }54 inline int getint()55 {56 register int num=0;57 register char ch;58 do ch=getchar(); while (ch<‘0‘ || ch>‘9‘);59 do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);60 return num;61 }62 inline void putint(long long num)63 {64 char stack[22];65 register int top=0;66 if (num==0) stack[top=1]=‘0‘;67 for ( ;num;num/=10) stack[++top]=num%10+‘0‘;68 for ( ;top;top--) putchar(stack[top]);69 putchar(‘\n‘);70 }
[vijos P1880]ファーラの力
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。