自动搬运

查看原文

来自洛谷，原作者为

	大头冲锋车丶 **

搬运于2025-08-24 21:36:39，当前版本为作者最后更新于2019-08-19 19:21:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们用 $dijkstra$ 来写。

与平常 $dijkstra$ 不同的是，此题还需要维护该条路上最大权值，故我们可以用一个$pre[i]$ 数组维护最优解这条路上的最大权值。

$dist[i]$ 存储的是根本意义上的最短路 （就是指再加上最长路的值，起点到 $i$ 点最短的权值，即题目所求。但是注意，这里的 $dist[]$ 存储的值是尚未再加上最长路的总值。）

因为有些路它不加两倍权值的话会导致比正确答案更短，这样记录就错了。 其次，像上面所说的，我们在放缩的时候，不应该用 $dist[]$ 直接存储我们需要的答案，即先不再加上最大权值。

所以我们最短路跑的应该是:

1、在真正意义上的最短路值却先没有再加上这条路最长权值的 $dist[i]$ 。

2、$pre[i]$ 始终保存的是，每次放缩后的真正意义的最短路上，最长路权值。

故我们最后输出 $dist[n] + pre[n]$ 即可。

此外注意的是：我们不需要用 $vis[]$ 标记已走过或已经处理最短路答案，然后不再更新。 这将会导致答案出错，因为可能从已经处理过的 $u$ 点 走到已经处理过的 $v$ 点，且更新到 $v$ 点的最短路。

比如样例中：根据优先队列顺序，到最后，会先更新节点 ⑦ ，再更新节点 ④，而如果标记 $vis[7]=true$ 的话，那么会导致 ④ --> ⑦ 这条路不再贡献于 $dist[7]$ ，导致答案出错。

代码如下：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#define maxn 108
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,cnt;
int head[maxn];
ll pre[maxn],dist[maxn];
bool vis[maxn];
struct Node
{
    int to;
    ll val;
    Node (){};
    Node(ll _val,int _to){
        to=_to,val=_val;
    }
    bool operator < (const Node &a) const{
        return val>a.val;
    }
};
struct Edge
{
    int to;
    ll val;
    int next;
}edge[2008<<1];
inline void add(int u,int v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].val=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
    return;
}
void dijkstra(int u)
{
    priority_queue<Node> q;
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++) {dist[i]=inf,vis[i]=false;pre[i]=0;}
    dist[u]=0;
    q.push(Node(0,1));
    while(!q.empty())
    {
        int u=q.top().to;
        ll t=dist[u];
        q.pop();
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if((dist[v]+pre[v]>t+edge[i].val+max(edge[i].val,pre[u]))){
                pre[v]=max(pre[u],edge[i].val);
                dist[v]=edge[i].val+t;
                q.push(Node(dist[v],v));
            }
        }
    }
    return;
}
int main()
{
    //freopen("test.in","r",stdin);
    scanf("%d%d",&n,&m);
    int A,B;
    ll C;
    for(int i=1;i<=m;i++){
        scanf("%d%d%lld",&A,&B,&C);
        add(A,B,C);add(B,A,C);
    }
    dijkstra(1);
    printf("%lld\n",dist[n]+pre[n] );
}