P2939 [USACO09FEB] Revamping Trails G 题解

· · 题解

说要分层图，不会！

直接开始乱搞

考虑 DP。

$dst[i][j]$ 表示编号为 $i$ 的点，经过 $j$ 次升级后的最短路。 每次的选择是：花费一次机会修建这条道路或者直接走。 那么易得状态转移方程为： $$ dst[i][j]=\min(dst[i][j],dst[nearestpoint][j-1],dst[nearestpoint][j]+w) $$ 复杂度$O(m\log n k)

AC code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10010;
const int K=30;
int n,m,k;
struct edge{
    int v,w;
    bool operator < (edge x) const{
        return w>x.w;
    }
};//结构体
vector<edge> g[N];
priority_queue<edge> pq;
int dis[N];
bool vis[N];
void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    pq.push((edge){1,0});
    while(!pq.empty()){
        int near_point=pq.top().v; pq.pop();
        if(vis[near_point]) continue;
        vis[near_point]=true;
        for(auto v:g[near_point]){
            if(!vis[v.v]){
                dis[v.v]=min(dis[near_point]+v.w,dis[v.v]);
                pq.push((edge){v.v,dis[v.v]});
            }
        }
    }
}//初始化
int dst[N][K];
void different_dijkstra(int x){
    memset(vis,0,sizeof(vis));
    pq.push((edge){1,0});
    while(!pq.empty()){
        int near_point=pq.top().v; pq.pop();
        if(vis[near_point]) continue;
        vis[near_point]=1;
//      cout<<"near_point: "<<near_point<<' '<<dst[near_point][x]<<"\n";
        for(auto v:g[near_point]){
            dst[1][x]=1e9;
            if(!vis[v.v]){
                dst[v.v][x]=min(min(dst[near_point][x-1],dst[near_point][x]+v.w),dst[v.v][x]);
                pq.push((edge){v.v,dst[v.v][x]});
            }
        }
    }
}//处理答案
signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w; cin>>u>>v>>w;
        g[u].push_back((edge){v,w});
        g[v].push_back((edge){u,w});
    }
    dijkstra();
    for(int i=1;i<=n;i++) dst[i][0]=dis[i];
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++) dst[j][i]=dst[j][i-1];
        different_dijkstra(i);
    }//依次计算
    int ans=1e9;
    for(int i=0;i<=k;i++) ans=min(ans,dst[n][i]);
  //因为路径上不一定会用完k次修建次数，所以答案是dst[n]中的最大值。
    cout<<ans;
    return 0;
}