1472G - Moving to the Capital（dijktra+dfs+dp）

1472G - Moving to the Capital

传送门

题意

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

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

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

思路

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

我用的方法是 Dijkstra + dfs 进行dp，先用Dijkstra 进行单点最短路的计算（算出 $d_i$ ），再对于所有的 $i\in [1,n]$ ，将所有 $d_i>d_j$ 的边用实线连接，其他用虚线连接。

之后对所有新的边进行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;
}