关键字：类次短路。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
每天早晨，小 Z 从家中穿过农场走到牛棚。农场由 N 块农田组成，农田通过 M 条双向道路连接，每条路有一定长度。小 Z 的房子在 1 号田，牛棚在 N 号田。没有两块田被多条道路连接，以适当的路径顺序总是能在农场任意一对田间行走。当小 Z 从一块田走到另一块时，总是以总路长最短的道路顺序来走。
小 Z 的牛呢，总是不安好心，决定干扰他每天早晨的计划。它们在 M 条路的某一条上安放一叠稻草堆，使这条路的长度加倍。牛希望选择一条路干扰使得小 Z 从家到牛棚的路长增加最多。它们请你设计并告诉它们最大增量是多少。
Input Format
第 1 行：两个整数 N, M。
第 2 到 M+1 行：第 i+1 行包含三个整数 A_i, B_i, L_i，A_i 和 B_i 表示道路 i 连接的田的编号，L_i 表示路长。
Output Format
第 1 行：一个整数，表示通过使某条路加倍而得到的最大增量。
Sample Input #1
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
Sample Output #1
2
Hint
【样例说明】
若使 3 和 4 之间的道路长加倍，最短路将由 1-3-4-5 变为 1-3-5。
【数据规模和约定】
对于 30%的数据，N <= 70，M <= 1,500。
对于 100%的数据，1 <= N <= 100，1 <= M <= 5,000，1 <= L_i <= 1,000,000。
一道类次短路问题。首先枚举在哪一条路上放置稻草。如果在不是最短路的边上放置稻草，由于最短路不变，小Z的路长也不变。所以，我们枚举最短路上的每一条边，将该边放置稻草后，跑一遍最短路。所有放置稻草后最短路的最大值与原最短路的差值就是答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <stdio.h>#include <string.h>#define QLEN 105int n,m,ans1,ans2 = 0;int e[10010][3],p[110];int q[110],from[110],dis[110],head,tail;short vis[110];int max(int a,int b){ return a>b?a:b;}void adde(int sn,int fn,int val,int id){ e[id][0] = fn; e[id][1] = val; e[id][2] = p[sn]; p[sn] = id; e[id+1][0] = sn; e[id+1][1] = val; e[id+1][2] = p[fn]; p[fn] = id+1;}void spfa(int ban,short mode){ int i,sn,fn,val; memset(dis,60,sizeof(dis)); head = 1; tail = 2; q[1] = 1; vis[1] = 1; dis[1] = 0; while(head != tail) { sn = q[head++]; for(i=p[sn];i;i=e[i][2]) { fn = e[i][0]; val = e[i][1]; if(i == ban || i == (ban^1)) val<<=1; if(dis[fn]<=dis[sn]+val) continue; dis[fn] = dis[sn]+val; if(mode) from[fn] = (i^1); if(vis[fn]) continue; vis[fn] = 1; q[tail++] = fn; if(tail>QLEN) tail = 1; } vis[sn] = 0; if(head>QLEN) head = 1; }}int main(){ int i,sn,fn,val; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&sn,&fn,&val); adde(sn,fn,val,i<<1); } spfa(0,1); ans1 = dis[n]; for(sn=n;sn!=1;sn=e[from[sn]][0]) { spfa(from[sn],0); ans2 = max(ans2,dis[n]); } printf("%d",ans2-ans1); return 0;} |
评论 (0)
