路【邻接矩阵存图找最短路】

问题 F: 路

传送门来源: upc12787

题目描述

Farmer John 热衷于散步，每天早上他都要从 1 号仓库走到 n 号仓库。 Farmer John 家的 n 个仓库被 m 条双向道路连通起来，每条道路有一个长度 w。而Farmer John 又不喜欢走路，所以他走的是从 1 号仓库到 n 号仓库的最短路。
但是 Farmer 的奶牛们总想搞点事情，他们计划着把 m 条道路的其中一条变成原来长度的 2 倍，使得 Farmer John 可能会多走一点路。
他们想知道，最多能让 Farmer John 多走多少路呢？

输入

第一行一个正整数 n,m，表示仓库个数和道路条数。
接下来 m 行，每行三个正整数，表示每条双向道路的连接的仓库和该双向道路的长度。

输出

输出只有一行，表示最多能让 Farmer John 每天早上多走多少路。

样例输入

样例输出

提示

一开始的最短路为1→3→4→5，长度为1+3+2=6。
将连接3和4的边变为原来的两倍，3×2=6。
改造后的图，最短路为1→3→5，长度为1+7=8。
多走了8−6=2的路程，可以证明这是最大的答案。
对于50%的数据，1≤n≤50。
对于100%的数据，1≤n≤250，1≤m≤25000，1≤w≤106。
保证没有重边。

思路：

邻接矩阵存图（用链式前向星+堆优化T了），先用迪杰斯特拉找最短路，记录长度sum，再暴力枚举每一条边，将其长度更改为2倍后用迪杰斯特拉找最短路，后恢复这条边的长度，取最大长度与sum取差值即为结果。

复杂度： O(m*n²)优化后可变为O(m*n*logn)

AC代码：

O(m*n²)该超时，可不知道怎么就过了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX=3e2;
const LL MAX1=3e4;
const LL INF=0x3f3f3f3f;
LL n,m,k;
LL dis[MAX+5];
LL a[MAX+5][MAX+5];
bool vis[MAX+5];

void diji(LL s)
{
    for(int i=1;i<=n;i++){
        dis[i]=a[s][i]; ///dis数组记录1点到该点的长度
        vis[i]=false;
    }
    vis[s]=true;
    while(1){
        LL k=-1,len=INF;
        for(LL i=1;i<=n;i++){
            if(!vis[i]&&len>dis[i]){
                len=dis[i];
                k=i;
            }
        }
        if(k==-1){
            break;
        }
        vis[k]=true;
        for(LL i=1;i<=n;i++){
            if(!vis[i]&&dis[i]>dis[k]+a[k][i]){
                dis[i]=dis[k]+a[k][i];
            }
        }
    }
}

struct node{
    LL u,v,w;
}edge[MAX1+5];
int main()
{
    scanf("%lld%lld",&n,&m);
    for(LL i=1;i<=n;i++){
        for(LL j=1;j<=n;j++){ ///邻接矩阵要初始化
            if(i==j) a[i][j]=0;
            else a[i][j]=INF;
        }
    }
    for(LL i=0;i<m;i++){
        LL u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        edge[i].u=u,edge[i].v=v,edge[i].w=w;
        a[u][v]=w;
        a[v][u]=w;
    }
    diji(1);
    LL sum=dis[n],maxx=-INF;
    for(int i=0;i<m;i++){
        LL u,v,w;
        u=edge[i].u,v=edge[i].v,w=edge[i].w; ///修改边长后恢复长度
        a[u][v]=2*w;
        a[v][u]=2*w;
        diji(1);
        maxx=max(maxx,dis[n]);
        a[u][v]=w;
        a[v][u]=w;
    }
    printf("%lld\n",maxx-sum);
    return 0;
}

路【邻接矩阵存图找最短路】

问题 F: 路

推荐阅读