图论模版

Dijkstra+邻接表（HDU 2544 最短路）

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define pret(a,b) memset(a,b,sizeof(a))
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MX= 20005 ;
     
    
   

    

     

    
    

     

      int n,m,top ;
     
    
   

    

     

    
    

     

      bool vis[MX] ;
     
    
   

    

     

    
    

     

      int d[MX] ;
     
    
   

    

     

    
    

     

      struct vertx // 与要查找顶点相关的第一个边序号
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int head ;
     
    
   

    

     

    
    

     

      }V[MX] ;
     
    
   

    

     

    
    

     

      struct Edge 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int v,w ;
     
    
   

    

     

    
    

     
 int next ; //下标和内容均为边序号
     
    
   

    

     

    
    

     

      }E[MX] ;
     
    
   

    

     

    
    

     

      void add_edge(int u,int v,int w) // 无向图
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       E[top].v=v ;
     
    
   

    

     

    
    

     

       E[top].w=w ;
     
    
   

    

     

    
    

     

       E[top].next=V[u].head ;
     
    
   

    

     

    
    

     

       V[u].head=top++ ;
     
    
   

    

     

    
    

     

       E[top].v=u ;
     
    
   

    

     

    
    

     

       E[top].w=w ;
     
    
   

    

     

    
    

     

       E[top].next=V[v].head ;
     
    
   

    

     

    
    

     

       V[v].head=top++ ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void init() // 初始化
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       pret(vis,false) ;
     
    
   

    

     

    
    

     

       pret(V,-1) ;
     
    
   

    

     

    
    

     

       top=0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void Dijkstra()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

     

       d[i]=INF ;
     
    
   

    

     

    
    

     

       d[0]=0 ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int min=INF,sx ;
     
    
   

    

     

    
    

     
 for(int j=0 ;j<n ;j++)
     
    
   

    

     

    
    

     
 if(!vis[j]&&d[j]<min)
     
    
   

    

     

    
    

     

       min=d[sx=j] ;
     
    
   

    

     

    
    

     
 if(min==INF)  break ;
     
    
   

    

     

    
    

     

       vis[sx]=true ;
     
    
   

    

     

    
    

     
 for(int j=V[sx].head ;j!=-1 ;j=E[j].next)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int sy=E[j].v ;
     
    
   

    

     

    
    

     
 if(!vis[sy]&&d[sx]+E[j].w<d[sy])
     
    
   

    

     

    
    

     

       d[sy]=d[sx]+E[j].w ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int u,v,w ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&u,&v,&w) ;
     
    
   

    

     

    
    

     

       u-- ; v-- ; // 下标从零开始
     
    
   

    

     

    
    

     

       add_edge(u,v,w) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       Dijkstra() ;
     
    
   

    

     

    
    

     
 printf("%d\n",d[n-1]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

Dijstra + 邻接表 + 优先队列

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define pret(a,b) memset(a,b,sizeof(a))
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MX= 20005 ;
     
    
   

    

     

    
    

     

      int n,m,top ;
     
    
   

    

     

    
    

     

      bool vis[MX] ;
     
    
   

    

     

    
    

     

      int d[MX] ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,w ;
     
    
   

    

     

    
    

     
 friend bool operator < (const node &a,const node &b)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 return a.w > b.w ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      struct vertx // 与要查找顶点相关的第一个边序号
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int head ;
     
    
   

    

     

    
    

     

      }V[MX] ;
     
    
   

    

     

    
    

     

      struct Edge
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int v,w ;
     
    
   

    

     

    
    

     
 int next ; //下标和内容均为边序号
     
    
   

    

     

    
    

     

      }E[MX] ;
     
    
   

    

     

    
    

     

      void add_edge(int u,int v,int w) // 无向图
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       E[top].v=v ;
     
    
   

    

     

    
    

     

       E[top].w=w ;
     
    
   

    

     

    
    

     

       E[top].next=V[u].head ;
     
    
   

    

     

    
    

     

       V[u].head=top++ ;
     
    
   

    

     

    
    

     

       E[top].v=u ;
     
    
   

    

     

    
    

     

       E[top].w=w ;
     
    
   

    

     

    
    

     

       E[top].next=V[v].head ;
     
    
   

    

     

    
    

     

       V[v].head=top++ ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void init() // 初始化
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       pret(vis,false) ;
     
    
   

    

     

    
    

     

       pret(V,-1) ;
     
    
   

    

     

    
    

     

       top=0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void Dijkstra()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 priority_queue<node>Q ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       d[i]=INF ;
     
    
   

    

     

    
    

     

       d[0]=0 ;
     
    
   

    

     

    
    

     

       node curt ;
     
    
   

    

     

    
    

     

       curt.x=0 ;curt.w=0 ;
     
    
   

    

     

    
    

     

       Q.push(curt) ;
     
    
   

    

     

    
    

     
 while(!Q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       curt=Q.top() ;
     
    
   

    

     

    
    

     

       Q.pop() ;
     
    
   

    

     

    
    

     
 int sx=curt.x ;
     
    
   

    

     

    
    

     
 if(vis[sx])  continue ; // 标记顶点
     
    
   

    

     

    
    

     

       vis[sx]=true ;
     
    
   

    

     

    
    

     
 for(int e=V[sx].head ; e!=-1 ;e=E[e].next) // 更新
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int sy=E[e].v ;
     
    
   

    

     

    
    

     
 if(d[sx]+E[e].w<d[sy])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       d[sy]=d[sx]+E[e].w ;
     
    
   

    

     

    
    

     

       curt.x=sy ;
     
    
   

    

     

    
    

     

       curt.w=d[sy] ;
     
    
   

    

     

    
    

     

       Q.push(curt) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int u,v,w ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&u,&v,&w) ;
     
    
   

    

     

    
    

     

       u-- ; v-- ; // 下标从零开始
     
    
   

    

     

    
    

     

       add_edge(u,v,w) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       Dijkstra() ;
     
    
   

    

     

    
    

     
 printf("%d\n",d[n-1]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

Spfa ( HDU 1874 畅通工程续 ) （别忘了在主函数里调用 init( ) 函数！！！）

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define pret(a,b) memset(a,b,sizeof(a))
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MX= 20005 ;
     
    
   

    

     

    
    

     

      int n,m,top ;
     
    
   

    

     

    
    

     

      bool vis[MX] ;
     
    
   

    

     

    
    

     

      int d[MX] ;
     
    
   

    

     

    
    

     

      struct vertx
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int head ;
     
    
   

    

     

    
    

     

      }V[MX] ;
     
    
   

    

     

    
    

     

      struct Edge
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int v,w ;
     
    
   

    

     

    
    

     
 int next ;
     
    
   

    

     

    
    

     

      }E[MX] ;
     
    
   

    

     

    
    

     

      void init()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       pret(vis,false) ;
     
    
   

    

     

    
    

     

       pret(V,-1) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       d[i]=INF ;
     
    
   

    

     

    
    

     

       top=0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void add_edge(int u,int v,int w)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       E[top].v=v ;
     
    
   

    

     

    
    

     

       E[top].w=w ;
     
    
   

    

     

    
    

     

       E[top].next=V[u].head ;
     
    
   

    

     

    
    

     

       V[u].head=top++ ;
     
    
   

    

     

    
    

     

       E[top].v=u ;
     
    
   

    

     

    
    

     

       E[top].w=w ;
     
    
   

    

     

    
    

     

       E[top].next=V[v].head ;
     
    
   

    

     

    
    

     

       V[v].head=top++ ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void Spfa(int s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 queue<int>q ;
     
    
   

    

     

    
    

     

       vis[s]=true ;
     
    
   

    

     

    
    

     

       d[s]=0 ;
     
    
   

    

     

    
    

     

       q.push(s) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int x=q.front() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     

       vis[x]=false ;
     
    
   

    

     

    
    

     
 for(int i=V[x].head ;i!=-1 ;i=E[i].next)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int p=E[i].v ;
     
    
   

    

     

    
    

     
 if(d[x]+E[i].w<d[p])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       d[p]=d[x]+E[i].w ;
     
    
   

    

     

    
    

     
 if(!vis[p])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

      //判断环放在这里面 vis[p]=true ;
     
    
   

    

     

    
    

     

       q.push(p) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int u,v,w,x,y ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&u,&v,&w) ;
     
    
   

    

     

    
    

     

       add_edge(u,v,w) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 scanf("%d%d",&x,&y) ;
     
    
   

    

     

    
    

     

       Spfa(x) ;
     
    
   

    

     

    
    

     
 printf("%d\n",d[y]==INF ? -1 : d[y]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/20689137