djkstra nlogn

秒速五厘米 2021-09-29 08:16 195阅读 0赞

#include<bits/stdc++.h>
    #define fi first
    #define se second
    #define  pii pair<int,int>
    using namespace std;
    const int maxn=2e2+10;
    const int inf = 0x3f3f3f3f;
    vector<int> vs[maxn];
    priority_queue<pii> que;
    int dis[maxn];
    
    void dij(int s){
        memset(dis,inf,sizeof(dis));
        que.push(pii(0,s));
        dis[s] = 0;
        while(!que.empty()){
            int u = que.top().se; que.pop();
            for(int i=0; i<vs[u].size(); i++)
            {
                int v = vs[u][i];
                if(dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    que.push(pii(-1*dis[v],v));
                }
            }
        }
    }
    int main()
    {
        while(1)
        {
    
            int n;   cin>>n;
    
            if(!n)   break;
            int l,r; cin>>l>>r;
            for(int i=1;i<=n;i++)
            {
                int x; cin>>x;
                if(i-x>=1) vs[i].push_back(i-x);
                if(i+x<=n) vs[i].push_back(i+x);
            }
            dij(l);
            for(int i=1;i<=n;i++)
                vs[i].clear();
            if(dis[r]!=inf) cout<<dis[r]<<endl;
            else  cout<<-1<<endl;
        }
    }

转载于:https://www.cnblogs.com/Andromeda-Galaxy/p/10127712.html

发表评论取消回复

表情：

评论列表（有 0 条评论，195人围观）

还没有评论，来说两句吧...

相关阅读

相关最长不上升子序列的优化（nlogn）

一般的DP写法： for (int i=1;i<=t;i++) { f[i]=1;

港控/mmm°/ 2022年09月30日 06:29/ 0 赞/ 137 阅读

相关最长上升子序列nlogn算法

这题目是经典的DP题目，也可叫作LIS（Longest Increasing Subsequence）最长上升子序列或者最长不下降子序列。很基础的题目，有两种算法，复杂度分

╰半橙微兮°/ 2022年08月20日 04:15/ 0 赞/ 159 阅读

相关最长上升子序列O(nlogn)

模板： include <iostream> include <cstdio> using namespace std; const

秒速五厘米/ 2022年08月17日 14:23/ 0 赞/ 129 阅读

相关算法复杂度O(nlogn)详解

首先看以下程序段： for（int i=1;i<=n;i++） \{ for(int j=1;j<=n;j+=i) \{ ..... //复杂度为O(1); \}

深碍√TFBOYSˉ_/ 2022年06月10日 07:23/ 0 赞/ 374 阅读

相关 o(1), o(n), o(logn), o(nlogn)

在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度, 这里进行归纳一下它们代表的含义: 这是算法的时空复杂度

水深无声/ 2022年05月16日 02:28/ 0 赞/ 208 阅读

相关 o(1), o(n), o(logn), o(nlogn)

由于平时接触算法比较少，今天看资料看到了o(1)，都不知道是什么意思，百度之后才知道是什么意思。描述算法复杂度时,常用o(1), o(

浅浅的花香味﹌/ 2022年02月25日 15:12/ 0 赞/ 297 阅读

相关最长上升子序列 nlogn

最长上升子序列有dp的写法 f\[i\]:=max（f\[j\]）+1; f\[1\]:=1; ![ContractedBlock.gif][] ![ExpandedBl

迈不过友情╰/ 2022年01月07日 09:39/ 0 赞/ 196 阅读

相关 O(1), O(n), O(logn), O(nlogn) 的区别

[https://blog.csdn.net/ted\_cs/article/details/82881831][https_blog.csdn.net_ted_cs_arti

柔情只为你懂/ 2021年12月22日 20:05/ 0 赞/ 390 阅读

相关时间复杂度为O(nlogn)的算法

mergeSort 口诀：左拆分，左合并，右拆分，右合并，最后合并左右。归并排序的逻辑归并排序的战略（宏观）逻辑先将原数组拆分为arr

柔情只为你懂/ 2021年10月01日 09:34/ 0 赞/ 372 阅读

相关 djkstra nlogn

include<bits/stdc++.h> define fi first define se second define pii pair

秒速五厘米/ 2021年09月29日 08:16/ 0 赞/ 196 阅读