dijistra模板

1 void dijistra(int x){ 2     int pos = x; 3     for(int i = 1; i <= n; i ++){ 4         dist[i] = g[i][pos]; 5     } 6     vis[pos] = true; 7     for(int i = 1; i <= n; i ++){ 8         int mins = INF; 9         for(int j = 1; j <= n; j ++){10             if(!vis[j] && dist[j] < mins){11                 pos = j;12                 mins = dist[j];13             }14         }15         vis[pos] = true;16         for(int j = 1; j <= n; j ++){17             if(!vis[j] && dist[j] > dist[pos] + g[pos][j]){18                 dist[j] = dist[pos] + g[pos][j];19             }20         }21     }22 }

 

优化的dijistra模板：

1 struct edge{ 2     int to, cost; 3 }; 4 vector
     
       g[N]; 5 typedef pair
      
        P; // first是最短距离，second是定点的编号 6 void dijistra(int s){ 7     priority_queue
       
        
,greater
        
 > que; 8     d[a] = 0; 9     que.push(P(0,s));10     while(!que.empty()){11         P p = que.top();que.pop();12         int v = p.second;13         if(d[v] < p.first) continue;14         for(int i = 0; i < g[v].size(); i ++){15             edge e = g[v][i];16             if(d[e.to] > d[v] + e.cost){17                 d[e.to] = d[v] + e.cost;18                 que.push(P(d[e.to],e.to));19             }20         }21     }22 }
       
      
     

 

 

Floyd模板，由于复杂度太大，很少用：

1 int d[MAX_N]d[MAX_N]; 2 int v; 3  4 void Floyd(){ 5     for(int k = 0; k < v; k ++){ 6         for(int i = 0; i < v; i ++){ 7             for(int j = 0; j < v; j ++){ 8                 d[i][j] = min(d[i][j],d[i][k] + d[k][j]); 9             }10         }11     }12 }