数据结构与算法分析 - 单源点最短路（Dijkstra+floyd+bellman_ford）

   1:  typedef pair<int,int> P;

   2:  #define N 101

   3:  #define INF 100000

   4:  int edges[N][N];

   5:  int dist[N];

   6:  int pre[N];

   7:  int cases,k,n,m;

   8:  void init(){

   9:      for(int i=0;i<N;i++){

  10:          for(int j=0;j<N;j++){

  11:              edges[i][j]=INF;

  12:              if(i==j)

  13:                  edges[i][j]=0;

  14:          }

  15:      }

  16:  }

  17:  void Dijkstra(int s,int t){

  18:      bool visited[N];

  19:      memset(visited,0,sizeof(visited));

  20:      visited[s]=true;

  21:      priority_queue<P,vector<P>,greater<P> > Q;

  22:      memset(pre,-1,sizeof(pre));

  23:      for(int i=0;i<N;i++)

  24:          dist[i]=INF;

  25:      dist[s]=0;

  26:      Q.push(P(0,s));

  27:      while(!Q.empty()){

  28:          P p=Q.top();

  29:          Q.pop();

  30:          int v=p.second;

  31:          if(dist[v]<p.first) continue;

  32:          for(int i=1;i<=n;i++){

  33:              int newedges=dist[v]+edges[v][i];

  34:              if(!visited[i]&&dist[i]>newedges){

  35:                  dist[i]=newedges;

  36:                  visited[i]=true;

  37:                  pre[i]=v;

  38:                  Q.push(P(dist[i],i));

  39:              }

  40:          }

  41:      }

  42:  }