hdu5521 ( Dijkstra )

题目描述：

给定一张图，问从1和n相遇的最短时间。

这道题的输入比较特殊，不能直接存，所以怎么输入，怎么存取，只要可以访问到一个节点的相邻节点就可以，由于spfa算法的时间复杂度为m*n，而Dijkstra算法的时间复杂度为m*log(n),

其实Dijkstra就是用优先队列替换掉了spfa中的普通队列，每次都是用权值最小的点去更新别人，可以这么理解，用用权值最小的点a去更新其他节点，在更新节点中必然会有一个节点已经是

最短路，假设是b，因为源点到其他节点的距离+其他节点到b节点的距离 > dist[a] + edge[a][b], 因为源点到其他节点的距离 > dist[a] + edge[a][b]；最多有10^6个点，那么可能就会有 10^12条边，时间复杂度为 10^12 * log(10^5) = 15*10^12;所以主要取决于有多少条边，分析一下如果一个节点已经更新了它所在集合中的其他点，那么这个集合中所有点之间的边就不会在更新了，假设a,b,c,d,e在一个集合里，集合之间的路径为edge，假设a是更新点，说明b，c，d，e的最短路大于a的最短路，说明b，c，d的最短路一定是由a得到，而不是 b，c，d，Dis[a]+edge < Dist[k] +edge，k属于b,c,d。所以集合只会被访问一次。

//有可能一个人在家等他

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#include <algorithm>

#include <math.h>

#define  maxn 1100000

#define  LL    long long

using namespace std;

int t;

int n,m;

vector < int >  G[maxn];

int tt[maxn],ss[maxn];

vector < int >  Set[maxn];

LL Dist[][maxn];

int vis[maxn];

int VISIT[maxn];

 LL answer[maxn];

 LL ans[maxn];

struct node

{

    int u,dist;

    friend bool operator < (node a,node b)

    {

        return a.dist>b.dist;

    }

};

void init()

{

    memset(vis,,sizeof(vis));

    memset(VISIT,,sizeof(VISIT));

}

void Dijkstra(int start)

{

    int kind;

    if(start==)

        kind=;

    else

        kind=;

    priority_queue < node >    que;

    node s;

    s.u=start;

    s.dist=;

    Dist[kind][start]=;

    que.push(s);

    while(!que.empty())

    {

       s=que.top();

       que.pop();

       if(vis[s.u]==)

        continue;

       vis[s.u]=;

       int from=s.u;

       for(int i=;i<Set[from].size();i++)  //找到所在集合

       {

          int j=Set[from][i]; //j代表哪个集合

          if(VISIT[j]==)

            continue;

          VISIT[j]=;

          int edge= tt[j]; //edge代表长度

          for(int k=;k<G[j].size();k++)  //遍历相邻节点

           {

              node Next;

              int to=G[j][k];

              if(Dist[kind][to]>Dist[kind][from]+edge  || Dist[kind][to]==- )

              {

                 Dist[kind][to]=Dist[kind][from] + edge;

                 Next.dist=Dist[kind][to];

                 Next.u=to;

                 que.push(Next);

              }

           }

       }

    }

}

void solve()

{

    init();

    Dijkstra();

    init();

    Dijkstra(n);

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

    {

       // cout<<Dist[1][i]<<" "<<Dist[2][i]<<endl;

        if(Dist[][i]==- || Dist[][i]==-)

            answer[i]=-;

        else

        answer[i]=max(Dist[][i],Dist[][i]);

    }

     LL MIN=-;

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

     {

         if(MIN > answer[i] || (MIN==-) )

            MIN=answer[i];

     }

     if(MIN==-)

        printf("Evil John\n");

     else

     {

          printf("%I64d\n",MIN);

          int flag=;

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

          {

              if(MIN==answer[i])

              {

                if(flag==)

                    printf(" ");

                printf("%d",i);

                flag=;

              }

          }

          printf("\n");

     }

}

void input()

{

        scanf("%d%d",&n,&m);

        for(int i=;i<=m;i++)

        {

            scanf("%d%d",&tt[i],&ss[i]);

            for(int j=;j<=ss[i];j++)

            {

                int input;

                scanf("%d",&input);

                G[i].push_back(input);

                Set[input].push_back(i);

            }

        }

}

void Init()

{

   for(int i=;i<maxn;i++)

   {

       G[i].clear(); Set[i].clear();

   }

    memset(Dist,-,sizeof(Dist));

}

int main()

{

    //freopen("test.txt","r",stdin);

    scanf("%d",&t);

    int Case=;

   // printf("%d\n",inf);

   // cout<<inf<<endl;

    while(t--)

    {

        Init();

        input();

        printf("Case #%d: ",++Case);

        solve();

    }

    return ;

}

巴特西

hdu5521 ( Dijkstra )

最新文章

热门文章