本文主要是介绍课上题目代码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
dijkstra和spfa区别 ：
dikstra是基于贪心的思想，每次选择最近的点去更新其它点，过后就不再访问。而在spfa算法中，只要有某个点的距离被更新了，就把它加到队列中，去更新其它点，所有每个点有被重复加入队列的可能。
或者跟具体的说区别在于diikstra总是要找到dist最小的元素来作为父节点更新其他点，而不是直接取队头元素(当然如果是优先队列也是取队头元素) :更新的顺序不同主要导致的差异是算法时间复杂度上的不同;功能上当然也造成了一定的区别，比如由于dikstra严格要求每次取的元素都是队列中最小的，这也导致了队头元素的dist值是单调递增的，从而一旦出现负权边就会破坏这个性质，从而导致找不到最优解。
图结构练习——最短路径 | SDUT OnlineJudge
#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define endl "\n"
#define int long long
#define pb push_back
typedef pair<int, int> PII;
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f;
int n, m;
int g[M][M];
void floyd()
{for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)g[i][j] = min(g[i][k] + g[k][j], g[i][j]);
}
signed main()
{Yshanqian;while (cin >> n >> m){memset(g, inf, sizeof g);for (int i = 1; i <= n; i++)g[i][i] = 0;for (int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;if (c < g[a][b])g[a][b] = g[b][a] = c;}floyd();cout << g[1][n] << endl;}return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define endl "\n"
#define int long long
#define pb push_back
typedef pair<int, int> PII;
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e4 + 10, M = 1010, inf = 0x3f3f3f3f;
int n, m;
int dis[N], st[N];
vector<PII> g[N];
void spfa()
{queue<int> q;for (int i = 1; i <= n; i++)dis[i] = 1e18;memset(st, 0, sizeof st);dis[1] = 0;q.push(1);st[1] = 1;while (q.size()){int u = q.front();q.pop();st[u] = 0;for (auto ed : g[u]){int v = ed.xx, w = ed.yy;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;if (!st[v])q.push(v);}}}
}
signed main()
{Yshanqian;while (cin >> n >> m){for (int i = 1; i <= n; i++)g[i].clear();for (int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;g[a].pb({b, c});g[b].pb({a, c});}spfa();cout << dis[n] << endl;}return 0;
}#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define endl "\n"
#define int long long
#define pb push_back
typedef pair<int, int> PII;
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f;
int n, m;
int dis[N], st[N];
vector<PII> g[N];
void dijkstra()
{priority_queue<PII, vector<PII>, greater<PII>> q;memset(dis, inf, sizeof dis);memset(st, 0, sizeof st);dis[1] = 0;q.push({0, 1});while (q.size()){int u = q.top().yy;q.pop();if (st[u])continue;st[u] = 1;for (auto ed : g[u]){int v = ed.xx, w = ed.yy;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({dis[v], v});}}}
}
signed main()
{Yshanqian;while (cin >> n >> m){for (int i = 1; i <= n; i++)g[i].clear();for (int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;g[a].pb({b, c});g[b].pb({a, c});}dijkstra();cout << dis[n] << endl;}return 0;
}数据结构实验之图论七：驴友计划
#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define endl "\n"
#define int long long
#define pb push_back
typedef pair<int, int> PII;
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f;
int n, m, s, t;
int dis[N], st[N], mon[N];
struct node
{int v, w, cost;
};
vector<node> g[N];
void dijkstra()
{priority_queue<PII, vector<PII>, greater<PII>> q;memset(dis, inf, sizeof dis);memset(st, 0, sizeof st);dis[s] = 0;q.push({0, s});while (q.size()){int u = q.top().yy;q.pop();if (st[u])continue;st[u] = 1;for (auto ed : g[u]){int v = ed.v, w = ed.w, cost = ed.cost;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;mon[v] = mon[u] + cost;q.push({dis[v], v});}else if (dis[v] == dis[u] + w){if (mon[v] > mon[u] + cost){mon[v] = mon[u] + cost;q.push({dis[v], v});}}}}
}
signed main()
{Yshanqian;int T;cin >> T;while (T--){cin >> n >> m >> s >> t;for (int i = 0; i <= n; i++)g[i].clear();for (int i = 1; i <= m; i++){int a, b, c, d;cin >> a >> b >> c >> d;g[a].pb({b, c, d});g[b].pb({a, c, d});}dijkstra();cout << dis[t] << " " << mon[t] << endl;}return 0;
}人活着系列之芳姐和芳姐的猪
#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define endl "\n"
#define int long long
#define pb push_back
typedef pair<int, int> PII;
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f;
int n, m, k;
int a[N], g[M][M];
void floyd()
{for (int k = 1; k <= m; k++)for (int i = 1; i <= m; i++)for (int j = 1; j <= m; j++)g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
signed main()
{Yshanqian;cin >> n >> m >> k;for (int i = 1; i <= n; i++)cin >> a[i];memset(g, inf, sizeof g);for (int i = 1; i <= m; i++)g[i][i] = 0;for (int i = 1; i <= k; i++){int a, b, c;cin >> a >> b >> c;if (c < g[a][b])g[a][b] = g[b][a] = c;}floyd();int ans = 1e18;for (int i = 1; i <= m; i++){int tmp = 0;for (int j = 1; j <= n; j++){int s = a[j];tmp += g[i][s];}ans = min(ans, tmp);}cout << ans << endl;return 0;
}这篇关于课上题目代码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
