最短路问题分为①②单源正权值最短路③④单源存在负权值的最短路⑤多源最短路①朴素Dijkstra适用于单源正权值且稠密图acwing849typedef pairint, int PII;int n, m;vectorvectorPIIgraph;vectorboolused;vectorintdist;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#includequeuetypedef pairint, int PII;int n, m;vectorvectorPIIgraph;vectorboolused;vectorintdist;priority_queuePII, vectorPII, greaterPIIh; //一定是小根堆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条边的时候有作用acwing853struct edge{int a, b, w;};int n, m, k;vectoredgegraph;vectorintdist;vectorintback_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;elsecout 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#includequeuetypedef pairint, int PII;int n, m;vectorvectorPIIgraph;vectorboolin; //这里不用used数组需要判断的是是否当前在queue中vectorintdist;queueintque;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;elsecout 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适用于多源最短路问题acwing854int n, m, k;vectorvectorintgraph;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, vectorint(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;elsecout graph[a][b] endl;}return 0;}