企业官网建设流程全解析

最短路问题分为①②单源正权值最短路③④单源存在负权值的最短路⑤多源最短路

①朴素Dijkstra：适用于单源正权值且稠密图

acwing849

typedef pair<int, int> PII;
int n, m;
vector<vector<PII>>graph;
vector<bool>used;
vector<int>dist;

void Dijkstra()
{
for (int q = 0; q < n; q++)
{
int curr = -1;
for (int i = 1; i <= n; i++)
{
if (!used[i] && (curr == -1 || dist[i] < dist[curr]))
curr = i;
}
if (curr == n) //可以提前结束
break;
used[curr] = true; //记得要更新状态
for (int i = 0; i < graph[curr].size(); i++)
{
int temp = graph[curr][i].first;
if (dist[temp] > dist[curr] + graph[curr][i].second)
dist[temp] = dist[curr] + graph[curr][i].second;
}
}
cout << ((dist[n] == 1e9) ? -1 : dist[n]) << endl;
}
int main()
{
cin >> n >> m;
graph.resize(n + 1);
used.resize(n + 1, false);
dist.resize(n + 1, 1e9);
dist[1] = 0;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[a].emplace_back(make_pair(b, c));
}
Dijkstra();
return 0;
}

②堆优化版Dijkstra：适用于单源正权值且稀疏图

acwing850

#include<queue>
typedef pair<int, int> PII;
int n, m;
vector<vector<PII>>graph;
vector<bool>used;
vector<int>dist;
priority_queue<PII, vector<PII>, greater<PII>>h; //一定是小根堆

void Dijkstra()
{
h.push({ 0,1 });
while (!h.empty())
{
auto curr = h.top();
h.pop();
if (used[curr.second])
continue;
used[curr.second] = true;
for (int i = 0; i < graph[curr.second].size(); i++)
{
auto temp = graph[curr.second][i];
if (dist[temp.first] > dist[curr.second] + temp.second)
{
dist[temp.first] = dist[curr.second] + temp.second;
h.push({ dist[temp.first] ,temp.first }); //注意堆插入的时机
}
}
}
cout << ((dist[n] == 1e9) ? -1 : dist[n]) << endl;
}
int main()
{
cin >> n >> m;
graph.resize(n + 1);
used.resize(n + 1, false);
dist.resize(n + 1, 1e9);
dist[1] = 0;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[a].emplace_back(make_pair(b, c));
}
Dijkstra();
return 0;
}

③bellman-for：会被④全方位取代，仅在限制最多使用k条边的时候有作用

acwing853

struct edge
{
int a, b, w;
};
int n, m, k;
vector<edge>graph;
vector<int>dist;
vector<int>back_up; //要增加备份数组

void bellman_ford()
{
for (int i = 0; i < k; i++)
{
for (int j = 1; j <= n; j++)
{
back_up[j] = dist[j];
}
for (int j = 0; j < graph.size(); j++)
{
auto curr = graph[j];
int a = curr.a;
int b = curr.b;
int w = curr.w;
if (back_up[a] != 1e9 && dist[b] > back_up[a] + w) //要注意备份数组的使用
dist[b] = back_up[a] + w;
}
}
if (dist[n] > 1e9 / 2)
cout << "impossible" << endl;
else
cout << dist[n] << endl;
}
int main()
{
cin >> n >> m >> k;
dist.resize(n + 1, 1e9);
dist[1] = 0;
back_up.resize(n + 1);
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
struct edge e;
e.a = a;
e.b = b;
e.w = w;
graph.push_back(e);
}
bellman_ford();
return 0;
}

④spfa：适用于单源存在负权值

acwing851

#include<queue>
typedef pair<int, int> PII;
int n, m;
vector<vector<PII>>graph;
vector<bool>in; //这里不用used数组，需要判断的是是否当前在queue中
vector<int>dist;
queue<int>que;

void spfa()
{
que.push(1);
in[1] = true;
while (!que.empty())
{
auto curr = que.front();
que.pop();
in[curr] = false;
for (int i = 0; i < graph[curr].size(); i++)
{
auto temp = graph[curr][i];
if (dist[temp.first] > dist[curr] + temp.second)
{
dist[temp.first] = dist[curr] + temp.second;
if (!in[temp.first])
{
que.push(temp.first);
in[temp.first] = true;
}
}
}
}
if (dist[n] > 1e9 / 2)
cout << "impossible" << endl;
else
cout << dist[n] << endl;
}
int main()
{
cin >> n >> m;
graph.resize(n + 1);
in.resize(n + 1, false);
dist.resize(n + 1, 1e9);
dist[1] = 0;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[a].emplace_back(make_pair(b, c));
}
spfa();
return 0;
}

⑤floyd：适用于多源最短路问题

acwing854

int n, m, k;
vector<vector<int>>graph;

void floyd()
{
for (int q = 1; q <= n; q++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
graph[i][j] = min(graph[i][j], graph[i][q] + graph[q][j]);
}
}
}

}
int main()
{
cin >> n >> m >> k;
graph.resize(n + 1, vector<int>(n + 1, 1e9));
for (int i = 1; i <= n; i++)
{
graph[i][i] = 0; //需要单独处理自环距离
}
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[a][b] = min(graph[a][b], c);
}
floyd();
while (k--)
{
int a, b;
cin >> a >> b;
if (graph[a][b] > 1e9 / 2)
cout << "impossible" << endl;
else
cout << graph[a][b] << endl;
}
return 0;
}