P2176 [USACO14FEB]路障Roadblock

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

说明/提示

【样例说明】

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

好吧，和上题神似，但需要将边乘2倍

#include<iostream>
#include<cstring>
#include<cstdio>
#define M 15000
#include<queue> 
#define N 110
using namespace std;
int n,m;
int po,ans;
int head[N],to[M],next[M],len[M],e=1;
void buid(int u,int v,int l)
{
    next[++e]=head[u],head[u]=e;
    to[e]=v,len[e]=l;
}
int dis[N],init[N];
int pre[N],fr[N],that[M],nu;
queue<int> q;
void spfa(int s)
{
    memset(dis,20,sizeof(dis));
    dis[s]=0;init[s]=1,q.push(s);
    while(!q.empty())
    {
        int now=q.front();q.pop();init[now]=0;
        for(int i=head[now];i;i=next[i])
        {
            int j=to[i];
            if(dis[j]>dis[now]+len[i])
            {
                dis[j]=dis[now]+len[i];
                pre[j]=i;fr[j]=now;
                if(!init[j])
                {
                    init[j]=1;q.push(j);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int u,v,l;
        scanf("%d%d%d",&u,&v,&l);
        buid(u,v,l);
        buid(v,u,l);
    }
    spfa(1);po=dis[n];
    int now=n;
    while(now!=1)
    {
        that[++nu]=pre[now];
        now=fr[now];
    }
    for(int i=1;i<=nu;++i)
    {
        len[that[i]]*=2;
        len[that[i]^1]*=2;
        spfa(1);
        ans=max(ans,dis[n]);
        len[that[i]]/=2;
        len[that[i]^1]/=2;
    }
    cout<<ans-po<<endl;
    return 0;
}

P2176 [USACO14FEB]路障Roadblock

标签：btn   ext   决定   define   格式   顺序   scanf   题目   mes