1472G - Moving to the Capital(dijktra+dfs+dp)

(22) 2024-04-03 13:01:01

1472G - Moving to the Capital

传送门

题意

给定一张 n n n m m m 边的有向图,顶点1为首都, d i d_i di 表示从城市 i i i 到首都的最短距离。

现在如果你在城市 i i i ,要去离首都尽可能近的地方,但是你在旅行时只能去一次满足 d j ≤ d i d_j \leq d_i djdi 的城市 j j j ,其他时候都只能去那些满足 d j > d i d_j > d_i dj>di 的城市 j j j ,或者终止旅程。

问从图中的每个点出发,离城市最近的距离是多少?

思路

参考:【Codeforces Round #693 (Div. 3) G】Moving to the Capital 很有意思的解法,

我用的方法是 Dijkstra + dfs 进行dp,先用Dijkstra 进行单点最短路的计算(算出 d i d_i di ),再对于所有的 i ∈ [ 1 , n ] i \in [1, n] i[1,n] ,将所有 d i > d j d_i \gt d_j di>dj 的边用实线连接,其他用虚线连接。

之后对所有新的边进行dfs:

  1. 实线的转移方程为 dp[i] = min(dp[i], dfs(j))

  2. 虚线的转移方程为 dp[i] = min(dp[i], d[j]) ,因为只能走一次虚线,不能继续dfs;

  3. 此外,还有 dp[i] = min(dp[i], d[i]) ,即留在原地不走;

  4. 另外,对于已经遍历过的部分要剪枝(不然超时)。

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pb push_back
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 2e5 + 19;
const ll mod = 1e9 + 7;

struct edge
{ 
   
    int v, w;
    edge(){ 
   }
    edge(int a, int b)
    { 
   
        v = a;
        w = b;
    }
    bool operator < (const edge& obj) const
    { 
   
        if(w == obj.w)
            return v < obj.v;
        return w > obj.w;
    }
};

vector<edge> es[N];
int dis[N];
int n, m;

vector<int> road[2][N];
int dp[N];

void addEdge(int u, int v, int w)
{ 
   
    es[u].pb({ 
   v, w});
}

void dij(int s)
{ 
   
    priority_queue<edge> que;
    dis[s] = 0;
    que.push({ 
   s, dis[s]});
    while(!que.empty())
    { 
   
        edge now = que.top();
        que.pop();
        for(int i = 0; i < es[now.v].size(); i++)
        { 
   
            edge to = es[now.v][i];
            if(dis[to.v] > now.w + to.w)
            { 
   
                dis[to.v] = now.w + to.w;
                que.push({ 
   to.v, dis[to.v]});
            }
        }
    }
}

void init(int n, int m)
{ 
   
    fill(dp, dp + n + 1, INF);
    fill(dis, dis + n + 1, INF);
    for(int i = 1; i <= n; i++)
    { 
   
        road[0][i].clear();
        road[1][i].clear();
        es[i].clear();
    }
}

int dfs(int x)
{ 
   
    if(dp[x] != INF)
        return dp[x];
    for(int i : road[0][x])
    { 
   
        dp[x] = min(dp[x], dfs(i));
    }
    for(int i : road[1][x])
    { 
   
        dp[x] = min(dp[x], dis[i]);
    }
    dp[x] = min(dp[x], dis[x]);
    return dp[x];
}

int main()
{ 
   
    int T;
    scanf("%d", &T);
    while(T--)
    { 
   
        scanf("%d%d", &n, &m);
        init(n, m);
        for(int i = 0; i < m; i++)
        { 
   
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v, 1);
        }
        dij(1);
        for(int i = 1; i <= n; i++)
        { 
   
            for(edge tmp : es[i])
            { 
   
                int j = tmp.v;
                if(dis[j] > dis[i])
                { 
   
                    road[0][i].pb(j);
                }
                else
                { 
   
                    road[1][i].pb(j);
                }
            }
        }
        for(int i = 1; i <= n; i++)
        { 
   
            if(dp[i] == INF)
            { 
   
                dfs(i);
            }
            cout << dp[i] << ' ';
        }
        cout << endl;
    }
    return 0;
}
THE END

发表回复