dijkstra_list_stl.cpp

ACM经典算法ACM经典算法ACM经典算法

//要包含的头文件,vector,map 

#include <iostream>
#include <vector>
#include <map>
#define maxn 1010
using namespace std;

typedef int weight; // 或double 
int n; // n nodes

//邻接表表示 
vector<int> r[maxn]; // r[i][j]: the j-th neighbor of i
vector<weight> e[maxn]; // e[i][j]: the length of edge i->r[i][j]
weight dist[maxn];//最短距离 
int pa[maxn];//路径 

multimap <weight, int> h;

void init() {
    int i;
    n=?;//此处为n赋值 
    for (i=0;i<n;i++) {
        r[i].clear();
        e[i].clear();
    }
    // 读图 
}
void dijkstra(int S) //S为始点 
{ // In the tree h, <weight, int> : <candidate distance, node id>
    weight d, tmp;
    int v, i, j;
    multimap<weight, int>::iterator it;
    h.clear();
    for (i=0;i<n;i++) dist[i]=-1;
    dist[S]=0;
    pa[S]=-1;
    h.insert(multimap<weight, int>::value_type(0, S));
    while (!h.empty()) {
        it=h.begin();
        v=it->second;
        d=it->first;
        h.erase(it);
        for (i=0;i<r[v].size();i++) {
            tmp=d+e[v][i];
            j=r[v][i];
            if (dist[j]<0 || tmp<dist[j]) {
                dist[j]=tmp;
                pa[j]=v;
                h.insert(multimap<weight, int>::value_type(tmp, j));
            }
        }
    }
}
//main()函数里要做的：调用init(),dijkstra(S).注意n为全局变量