codeforces 689 Mike and Shortcuts(最短路)

任意两点的距离是序号差，那么相邻点之间建边即可，同时加上题目提供的边
跑一遍dijkstra可得1点到每个点的最短路，时间复杂度是O(mlogm)

#include <cstdio>

#include <iostream>

#include <cstring>

#include <queue>

#include <vector>

using namespace std;

const int Max=200000+10;

int abs(int x) {return x>=0?x:-x;}

int n,m;

struct Edge{

int from,to,dist;

Edge(int u,int v,int d):from(u),to(v),dist(d){}

};

vector <Edge> edges;

vector <int>  G[Max];

int d[Max];

void Init()

{

    for(int i=0;i<=n;i++) G[i].clear();

    edges.clear();

}

void AddEdge(int from,int to,int dist)

{

    edges.push_back(Edge(from,to,dist));

    m=edges.size();

    G[from].push_back(m-1);

}

struct node

{

    int d,u;

    node(int dd,int uu):d(dd),u(uu){};

    bool operator < (const node & rhs) const {

    return d>rhs.d;

    }

};

const int INF=0x3f3f3f3f;

bool done[Max];

void Dijkstra(int s)

{

    priority_queue<node>Q;

    for(int i=1;i<=n;i++) d[i]=INF;

    d[s]=0;

    memset(done,0,sizeof(done));

    Q.push(node(0,s));

    while(!Q.empty())

    {

        node x=Q.top();Q.pop();

        int u=x.u;

        if(done[u]) continue;

        done[u]=true;

        for(int i=0;i<G[u].size();i++)

        {

            Edge &e=edges[G[u][i]];

            if(d[e.to]>d[u]+e.dist)

            {

                d[e.to]=d[u]+e.dist;

                Q.push(node(d[e.to],e.to));

            }

        }

    }

}

int main()

{

    while(~scanf("%d",&n))

    {

       int x;

       Init();

       for(int i=1;i<=n;i++)

       {

           scanf("%d",&x);

           AddEdge(i-1,i,1);

           AddEdge(i+1,i,1);

           AddEdge(i,x,1);

       }

       Dijkstra(1);

       for(int i=1;i<=n;i++)

       {

           if(i!=1) printf(" ");

           printf("%d",d[i]);

       }

       puts("");

    }

    return 0;

}

巴特西

codeforces 689 Mike and Shortcuts(最短路)

codeforces 689 Mike and Shortcuts(最短路)

最新文章

热门文章