题解 | #青蛙#

搜索dp，背包，点击这道题，然后图论解决......

题目可以抽象成每一个点 i,i+1之间都有度数为1的边连接，在此基础上还额外给出了其它度数为1的边

套dijkstra模板即可

using namespace std;
const int N = 1e3 + 10;
const int inf = 2e30 - 1;
typedef pair<int, int> PII;
int n, m, root;
vector<pair<int, int>> g[N];
int dis[N];
bool vis[N];
void dijkstra()
{
    for (int i = 1; i <= n; i++)
    {
        dis[i] = inf;
    }
    dis[root] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> qu;
    qu.push({dis[root], root});
    while (qu.size())
    {
        int u = qu.top().second;
        qu.pop();
        if (vis[u])
        {
            continue;
        }
        vis[u] = true;
        for (auto [v, w] : g[u])
        {
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                qu.push({dis[v], v});
            }
        }
    }
}
int main()
{
    cin >> n >> m ;
    root=0;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v ;
        w=1;
        g[u].push_back({v, w});
    }
    for (int i=0;i<=n;i++)
    {
        g[i].push_back({i+1,1});
        g[i+1].push_back({i,1});
    }
    dijkstra();
   cout<<dis[n];
}

纪念第一篇题解