本文共 1350 字，大约阅读时间需要 4 分钟。
SPFA模板题，题目中数据可能有两个点之间有多条边直接相连，使用 unordered_map< int, unordered_map< int, int>>, 来存储图的结构，可以方便的去除重边。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define max(a, b) (a) > (b)? (a) : (b)#define min(a, b) (a) < (b)? (a) : (b)unordered_map > gMap;int gMinDist[100005];bool gInQueue[100005];int Spfa(int s, int t) { queue Q; Q.push(s); memset(gMinDist, -1, sizeof(gMinDist)); memset(gInQueue, false, sizeof(gInQueue)); gMinDist[s] = 0; gInQueue[s] = true; //题目中不存在负权边，因此不需要检查有负权回路。检查存在负权回路，则需要通过 //判断否个点是否被更新超过 N 次，N为点的总数 while (!Q.empty()) { int u = Q.front(); Q.pop(); gInQueue[u] = false; for (auto x : gMap[u]) { int v = x.first; if (gMinDist[v] == -1 || gMinDist[v] > gMinDist[u] + x.second) { gMinDist[v] = gMinDist[u] + x.second; if (!gInQueue[v]) { //如果不存在队列中，则加入队列。剪枝优化 Q.push(v); } } } } return gMinDist[t];}int main() { int n, m, s, t; int u, v, d; scanf("%d %d %d %d", &n, &m, &s, &t); for (int i = 0; i < m; i++) { scanf("%d %d %d", &u, &v, &d); //用 unordered_map 存储图的结构，可以方便的去除重边 if (gMap.find(u) == gMap.end() || (gMap[u].find(v) == gMap[u].end() || gMap[u][v] > d)) { gMap[u][v] = d; gMap[v][u] = d; } } int min_dist = Spfa(s, t); printf("%d\n", min_dist); return 0;}
转载地址：http://kxiel.baihongyu.com/