关键字：类次短路。
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的路长也不变。所以，我们枚举最短路上的每一条边，将该边放置稻草后，跑一遍最短路。所有放置稻草后最短路的最大值与原最短路的差值就是答案。
#include <stdio.h>
#include <string.h>
#define QLEN 105
int 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)
