题解：B4165 [BCSP-X 2024 12 月初中组] 贸易

· · 题解

一条路径的长度为 \sum w-\max w+\min w。

转换题意：一条路径的长度为，在总长的基础上任意选出一条边减去、一条边再加一次。求最短路。

本题关键在于：该转换不影响答案。

原因是，确定路径后最优方案一定是删去最大值、翻倍最小值，满足题意。

此处有重要思想：最优化问题放宽限制后，如果非法解必然较劣，那么这一转换是正确的。

那么就是一个很简单的 dp 了，令 f_{u,a,b} 表示走到点 u，是否已经删去/增加一边的最短路。dijkstra 转移即可。

注意特判一条边的情况，此时增删等同于没有进行。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=2e5+10;
int n,m,q;
LL f[N][2][2];
bool vis[N*5];
vector<pair<int,int>>e[N];

void dijk(){
    priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>>q;
    memset(f,0x3f,sizeof(f));f[1][0][0]=0;
    q.push({0,1<<2});
    while(q.size()){
        int u=q.top().second;q.pop();
        if(vis[u])continue;vis[u]=1;
        int a=u>>1&1,b=u&1;u>>=2;
//      printf("%d %d %d\n",u,a,b);
        for(auto E:e[u]){
            int v=E.first,w=E.second;
            if(f[v][a][b]>f[u][a][b]+w)q.push({f[v][a][b]=f[u][a][b]+w,v<<2|b|a<<1});
            if(!a&&f[v][1][b]>f[u][0][b]+2*w)q.push({f[v][1][b]=f[u][0][b]+2*w,v<<2|b|2});
            if(!b&&f[v][a][1]>f[u][a][0])q.push({f[v][a][1]=f[u][a][0],v<<2|1|a<<1});
        }
    }
}

signed main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back({y,z});
        e[y].push_back({x,z});
    }
    dijk();
    while(q--){
        int i;scanf("%d",&i);
        printf("%lld\n",min(f[i][0][0],f[i][1][1]));
    }
    return 0;
}