Codeforces 1473 E. Minimum Path

Educational Codeforces Round 102 (Rated for Div. 2) E. Minimum Path

Description

给一个带权无向图，求从1点出发到每个点的最小$\sum{i=1}^{k}w{ei}-max{i=1}^{k}w{e_i}+min{i=1}^{k}w_{e_i}$，$e_i$是 $1$ 到 $x$ 上的路径。

Solution

观察到$\sum{i=1}^{k}w{e_i}$是求最短路。加上后面两项相当于变形为分层图：多的两项相当于对边进行了两次操作。

将这个问题转化为:跑最短路，你可以且必须进行如下两种操作:
1.选择路径上的一条边，减去它的边权
2.选择路径上的一条边，再加一次它的边权。

那么$dis[i][0/1][0/1]$代表从 $1$ 到 $i$ 点，是否已经使用了操作$1$，是否已经使用了操作$2$的最小值。那么答案就是 $dis[i][1][1]$.

正确性：很显然，对于任意一条路径，我们肯定是减去最大边权，加上最小边权。但问题是我们在跑最短路的过程中不知道哪条边会是最终的最小边权/最大边权(有后效性)。对状态升维表达出所有状态来消除后效性。

Code

vector<pii> e[maxn];
int dis[maxn][2][2], vis[maxn][2][2];
struct node {
    int u , dis , a1 , a2;
    friend int operator < (node const &a , node const& b){
        return a.dis > b.dis;
    }
};
void dijstra(){
    dis[1][0][0] = 0;
    priority_queue<node>q;
    q.push({1, 0 ,0, 0});
    while(not q.empty()){
        node fr = q.top();
        q.pop();
        int u = fr.u, a1 = fr.a1, a2 = fr.a2;
        if(vis[u][a1][a2]) continue;
        vis[u][a1][a2] = 1;
        for(auto x : e[u]){
            int v = x.fi, w = x.se;
            if(dis[v][a1][a2] > dis[u][a1][a2] + w){
                dis[v][a1][a2] = dis[u][a1][a2] + w;
                q.push({v, dis[v][a1][a2], a1 , a2});
            }
            if(!a1){
                if(dis[v][1][a2] > dis[u][0][a2]){
                    dis[v][1][a2] = dis[u][0][a2];
                    q.push({v, dis[v][1][a2], 1 , a2});
                }
            }
            if(!a2){
                if(dis[v][a1][1] > dis[u][a1][0] +  w + w ){
                    dis[v][a1][1] = dis[u][a1][0] +  w + w;
                    q.push({v,dis[v][a1][1],a1,1});
                }
            }
        }
    }
}
int32_t main()
{
    int n , m;
    cin >> n >> m;
    memset(dis , INF, sizeof dis);
    while(m -- ){
        int u ,v , w;
        cin >>u >> v >> w;
        if(u > v)swap(u , v);
        if(u == 1) dis[v][1][1] = w;
        e[u].eb(v , w);
        e[v].eb(u , w);
    }
    dijstra();
    for(int i = 2; i <= n; i++){
        cout << dis[i][1][1] << " \n"[i == n];
    }
    return 0;
}