洛谷 P2176 [USACO14FEB]路障Roadblock

题目描述

每天早晨，FJ从家中穿过农场走到牛棚。农场由 N 块农田组成，农田通过 M 条双向道路连接，每条路有一定长度。FJ 的房子在 1 号田，牛棚在 N 号田。没有两块田被多条道路连接，以适当的路径顺序总是能在农场任意一对田间行走。当FZ从一块田走到另一块时，总是以总路长最短的道路顺序来走。

FJ 的牛呢，总是不安好心，决定干扰他每天早晨的计划。它们在 M 条路的某一条上安放一叠稻草堆，使这条路的长度加倍。牛希望选择一条路干扰使得FJ 从家到牛棚的路长增加最多。它们请你设计并告诉它们最大增量是多少。

输入输出格式

输入格式：

第 1 行：两个整数 N, M。

第 2 到 M+1 行：第 i+1 行包含三个整数 A_i, B_i, L_i，A_i 和 B_i 表示道路 i 连接的田的编号，L_i 表示路长。

输出格式：

第 1 行：一个整数，表示通过使某条路加倍而得到的最大增量。

输入输出样例

输入样例#1：

输出样例#1：

说明

【样例说明】

若使 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。

先跑最短路

记录路径以便只修改有用的边

然后只改经过的边

跑最短路更新答案就好了

屠龙宝刀点击就送

#include <cstring>
#include <cstdio>
#include <queue>
#define N 5005
using namespace std;
int nextt[N<<1],to[N<<1],val[N<<1],head[N<<1],cnt=1,n,m,dist[N],pre[N];
inline void ins(int u,int v,int w)
{
    nextt[++cnt]=head[u];
    to[cnt]=v;
    val[cnt]=w;
    head[u]=cnt;
}
struct node
{
    int x,y;
    bool operator<(node a)const
    {
        return y>a.y;
    }
};
priority_queue<node>q;
bool vis[N];
int dijkstra(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    q.push((node){s,dist[s]});
    for(node now;!q.empty();)
    {
        now=q.top();q.pop();
        if(vis[now.x]) continue;
        vis[now.x]=1;
        for(int i=head[now.x];i;i=nextt[i])
        {
            int v=to[i];
            if(dist[v]>dist[now.x]+val[i])
            {
                dist[v]=dist[now.x]+val[i];
                pre[v]=now.x;
                q.push((node){v,dist[v]});
            }
        }
    }
    return dist[n];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int x,y,z,i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        ins(x,y,z);ins(y,x,z);
    }
    int Minx=dijkstra(1);
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=head[i];j;j=nextt[j])
        {
            int v=to[j],w=val[j];
            if(pre[i]==v||pre[v]==i)
            {
                val[j]=w*2;
                val[j^1]=w*2;
                ans=max(ans,dijkstra(1)-Minx);
                val[j]=w;
                val[j^1]=w;
            }
        }
    }
    printf("%d
",ans);
    return 0;
}