单源最短路 Dijkstra O(mlogn) (类实现)
#include <iostream>
#include <vector>
#include <map>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define maxn 1010
using namespace std;
typedef double weight;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
class graph_c
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
public:
void init(int _n);
void dijkstra(int S);
void add_edge(int u, int v, weight w);
private:
int n;
vector <int> r[maxn];
vector <weight> e[maxn];
weight dist[maxn];
int pa[maxn];
multimap <weight, int> h;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void graph_c::init(int _n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
n = _n;
for (int i = 0; i < n; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
r[i].clear();
e[i].clear();
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void graph_c::add_edge(int u, int v, weight w)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
r[u].push_back(v);
e[u].push_back(w);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void graph_c::dijkstra(int S)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
weight d, tmp;
int v;
multimap<weight, int>::iterator it;
h.clear();
for (int 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())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
it = h.begin();
v = it->second;
d = it->first;
h.erase(it);
for (int i = 0; i < r[v].size(); i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tmp = d + e[v][i];
int j = r[v][i];
if (dist[j] < 0 || tmp < dist[j])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dist[j] = tmp;
pa[j] = v;
h.insert(multimap<weight, int>::value_type(tmp, j));
}
}
}
}