堆优化的Dijkstra
typedef pair<int, int> P; //first为边的权值,second为点的编号
const int N = 100005;
int dis[N];
vector<P>e[N]; //first为点的编号, second为边的权值
priority_queue<P, vector<P>, greater<P> >q;
void dij(int s)
{
for (int i = 1; i <= N; ++i) dis[i] = 0xffffff;
dis[s] = 0;
while (!q.empty()) q.pop();
q.push(P(0, s));
while (!q.empty())
{
P c = q.top(); q.pop();
if (dis[c.second] < c.first)
continue;
for (int i = 0; i < e[c.second].size(); ++i)
{
int v = e[c.second][i].first;
int w = e[c.second][i].second;
if (dis[v] > c.first + w)
{
dis[v] = c.first + w;
q.push(P(dis[v], v));
}
}
}
}
普通Dijkstra
const int N = 5005;
bool book[N];
int dis[N];
int e[N][N]; //e最开始要初始化为0xffffff,e[i][i]设为0
void dij(int s)
{
book[s] = true;
for (int i = 1; i <= N; ++i)
dis[i] = e[s][i];
for (int i = 1; i < N; i++)
{
int u, min = 0xffffff;
for (int j = 1; j <= n; j++)
if (!book[j] && min > dis[j])
{
min = dis[j];
u = j;
}
book[u] = 1;
for (int v = 1; v <= n; v++)
if (e[u][v] != 0xffffff && dis[v] > dis[u] + e[u][v])
dis[v] = dis[u] + e[u][v];
}
}
SPFA
const int M = 250005;
const int N = 100005;
struct edge
{
int to, next, w;
}e[M << 1];
int cnt, head[N]
bool vis[N];
void spfa(int s, long long d[])
{
for (int i = 0; i < n; ++i) d[i] = 0xfffffff;
memset(vis, false, sizeof(vis));
queue<int>q;
d[s] = 0;
vis[s] = true;
q.push(s);
while (!q.empty())
{
int u = q.front(); q.pop();
vis[u] = false;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
int w = e[i].w;
if (d[v] <= d[u] + w) continue;
d[v] = d[u] + w;
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
网友评论