CCC2025 D

· · 题解

思路

M=N-1

图是一颗树，任意两点间路径唯一。从 1 开始搜索，记录走到每一个点时的花费和当前温度。时间复杂度 O(N)。

1\le c_i\le10

可以把每个点拆成十个走最短路，新点中每个点表示对应到达旧点的某个温度。时间复杂度 O(cN\log(cN)+cM)。

每个点出边数量 \le5

还是拆点，每个点表示对应旧点出发时的温度。令 \text{num}\leftarrow5，时间复杂度 O(\text{num}N\log(\text{num}N)+M)。

无特殊限制

一条路径的总花费是这条路径上所有相邻的两条边温度之差。

考虑把每一条边看作一个新点，这个问题相当于是在每两条共点边之间连一条新边，新边长为两条边的温度差，求一条与 1 相连的边到与 N 相连的边的最短路。要额外累加与 1 相连的边的 c。

这样连边是不行的，如果有一个菊花图显然任意两条边都是共点边，需要的新边数量量级达到 M^2。

我们需要从这一道题的性质上入手优化。发现新边长是新点权差，那么我们其实并不用给一个点所有的邻边都两两连新边，而是把这些边按温度排序，温度大小相邻的边之间连新边就行了，因为温度大小不相邻的边互相抵达可以通过温度在中间的点中转，而不影响消耗。

新边量级为 O(M)，再建一个超级源点导向 1 的邻边，超级汇点由 N 的邻边导向，跑这两点之间的最短路就好了。

时间复杂度 O(M\log M)。

还有一种做法，延续每个点出度 \le5 的做法，还是拆点，和它相连的边的每个温度都拆出一个点，同一个旧点的温度相邻的新点之间连边，时间复杂度 O(M\log M)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,w;
long long dis[300000];
bool vis[300000];
vector<pair<int,int>>e[300000],ne[300000];
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
inline void shortest_path(){//最短路板子 
    while(q.size()){
        int u = q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto [v,w] : e[u]) if(dis[v] > dis[u] + w) q.push({dis[v] = dis[u] + w,v});
    }
    return;
}
int main(){
    memset(dis,0x3f,sizeof(dis));
    read(n,m);
    for(int i = 1;i <= m;i ++) read(u,v,w),ne[u].push_back({w,i}),ne[v].push_back({w,i});//旧边只需要保存温度和边编号 
    for(int i = 2;i < n;i ++){
        sort(ne[i].begin(),ne[i].end());//给一个点的邻边按温度排序 
        for(int j = 1;j < ne[i].size();j ++){//任意温度相邻的边之间连新边 
            e[ne[i][j].second].push_back({ne[i][j - 1].second,abs(ne[i][j].first - ne[i][j - 1].first)});
            e[ne[i][j - 1].second].push_back({ne[i][j].second,abs(ne[i][j].first - ne[i][j - 1].first)});
        }
    }
    for(auto i : ne[1]) e[0].push_back({i.second,i.first});//超级源点 0 号新点 
    for(auto i : ne[n]) e[i.second].push_back({m + 1,0});//超级汇点 M+1 号新点 
    dis[0] = 0,q.push({0,0});
    shortest_path();
    printf("%lld",dis[m + 1]);
    return 0;
}