第六十一天 第十一章：图论part10 Bellman_ford 队列优化算法（又名SPFA） bellman_ford之判断负权回路 bellman_ford之单源有限最短路 (纯代码)

#include <iostream>

#include <vector>

#include <queue>

#include <list>

#include <climits>

using namespace std;

struct Edge { //邻接表

int to; // 链接的节点

int val; // 边的权重

Edge(int t, int w): to(t), val(w) {} // 构造函数

};

int main() {

int n, m, p1, p2, val;

cin >> n >> m;

vector<list<Edge>> grid(n + 1); // 邻接表

// 将所有边保存起来

for(int i = 0; i < m; i++){

cin >> p1 >> p2 >> val;

// p1 指向 p2，权值为 val

grid[p1].push_back(Edge(p2, val));

}

int start = 1; // 起点

int end = n; // 终点

vector<int> minDist(n + 1 , INT_MAX);

minDist[start] = 0;

queue<int> que;

(start); // 队列里放入起点

while (!()) {

int node = (); ();

for (Edge edge : grid[node]) {

int from = node;

int to = edge.to;

int value = ;

if (minDist[to] > minDist[from] + value) { // 开始松弛

minDist[to] = minDist[from] + value;

(to);

}

}

}

if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点

else cout << minDist[end] << endl; // 到达终点最短路径

}