图论算法 待补充
#includeusing namespace std;#include#includestruct edge {int s, e, v; //起点，终点，边权};edge edg[200005]; //存储两次int n, m, s, ans[100005], cnt;void add_edge(int a, int b, int c) {edg[cnt].s = a;edg[cnt].e = b;edg[cnt].v = c;cnt++;}int main() {memset(ans, 0x3f, sizeof(ans));scanf_s("%d%d%d", &n, &m, &s);for (int i = 0; i < m; i++) {int a, b, c;scanf_s("%d%d%d", &a, &b, &c);add_edge(a, b, c);add_edge(b, a, c);}ans[s] = 0;for (int i = 0; i < n; i++) {int f = 0;for (int j = 0; j ans[s] + v) {ans[e] = ans[s] + v;f = 1;}}if (!f)break;}for (int i = 1; i <= n; i++) {if (ans[i] == 0x3f3f3f3f)puts("-1");elseprintf("%d\n", ans[i]);}return 0;}2. 链式前向星+迪杰斯特拉
#include#include#include#includeusing namespace std;struct edge {int e, v, nnext; //终点，权重，下一个点的下标};struct node {int now, dis;bool operatordis > b.dis;}};edge edg[1000005];int n, m, s, ans[100005], head[100005], cnt;void add_edge(int a, int b, int c) {edg[cnt].e = b;edg[cnt].v = c;edg[cnt].nnext = head[a];head[a] = cnt++;}int main() {memset(head, -1, sizeof(head));memset(ans, 0x3f, sizeof(ans));scanf_s("%d%d%d", &n, &m, &s);for (int i = 0; i < m; i++) {int a, b, c;scanf_s("%d%d%d", &a, &b, &c);add_edge(a, b, c);add_edge(b, a, c);}priority_queueque;que.push(node{ s,0 });ans[s] = 0;while (!que.empty()) {node temp = que.top();que.pop();if (ans[temp.now] ans[temp.now] + v) {ans[e] = ans[temp.now] + v;que.push(node{ e,ans[e] });}}}for (int i = 1; i <= n; i++) {if (ans[i] == 0x3f3f3f3f)puts("-1");elseprintf("%d\n", ans[i]);}return 0;}3. 链式前向星+基于队列优化的贝尔福特曼
#include#include#include#includeusing namespace std;struct edge {int e, v, nnext;};edge edg[200005]; //存储两次int n, m, s, ans[100005], head[100005], mark[100005], cnt;void add_edge(int a, int b, int c) {edg[cnt].e = b;edg[cnt].v = c;edg[cnt].nnext = head[a];head[a] = cnt++;}int main() {memset(ans, 0x3f, sizeof(ans));memset(head, -1, sizeof(head));scanf_s("%d%d%d", &n, &m, &s);for (int i = 1; i <= m; i++) {int a, b, c;scanf_s("%d%d%d", &a, &b, &c);add_edge(a, b, c);add_edge(b, a, c);}queue que;ans[s] = 0;que.push(s);mark[s] = 1;while (!que.empty()) {int temp = que.front();que.pop();mark[temp] = 0;for (int i = head[temp]; i != -1; i = edg[i].nnext) {int e = edg[i].e, v = edg[i].v;if (ans[e] > ans[temp] + v) {ans[e] = ans[temp] + v;if (mark[e] == 0) {que.push(e);mark[e] = 1;}}}}for (int i = 1; i <= n; i++) {if (ans[i] == 0x3f3f3f3f)puts("-1");elseprintf("%d\n", ans[i]);}return 0;}4. 邻接表+迪杰斯特拉
#include#include#include#include#includeusing namespace std;int n, m, s, ans[100005];struct node {int now, dis;//小顶堆需要重载大于号bool operatordis > b.dis;}};struct edge {int e, v; //e终点，v权重};int main() {memset(ans, 0x3f, sizeof(ans));scanf_s("%d%d%d", &n, &m, &s);vector<vector >edg(n + 5, vector());for (int i = 0; i < m; i++) {int a, b, c;scanf_s("%d%d%d", &a, &b, &c);edg[a].push_back(edge{ b,c });edg[b].push_back(edge{ a,c });}priority_queueque;que.push(node{ s,0 });ans[s] = 0; while (!que.empty()) {node temp = que.top();que.pop();if (ans[temp.now] < temp.dis) {continue;}for (int i = 0; i temp.dis + v) {ans[e] = temp.dis + v;que.push(node{ e,ans[e] });}}}for (int i = 1; i <= n; i++) {if (ans[i] == 0x3f3f3f3f)puts("-1");elseprintf("%d\n", ans[i]);}return 0;}5. 邻接矩阵+弗洛伊德
#include#include#includeusing namespace std;int ans[1005][1005], n, m, s;int main() {memset(ans, 0x3F, sizeof(ans));scanf_s("%d%d%d", &n, &m, &s);for (int i = 1; i c) {ans[a][b] = c;ans[b][a] = c;}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {ans[j][k] = min(ans[j][k], ans[j][i] + ans[i][k]);}}}for (int i = 1; i <= n; i++) {ans[i][i] = 0;if (ans[s][i] == 0x3F3F3F3F) {puts("-1");}else {printf("%d\n", ans[s][i]);}}return 0;}