8
16
2015
0

[题解]小Z的可恶路障

关键字:类次短路。

Link&Limit


[洛谷2176]

时间限制: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;
}
Category: 题解 | Tags: 图论 最短路 洛谷 | Read Count: 525

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com