电影网站建设目的,国内c2c平台有哪些,建筑企业入渝备案查询,做网站找俊义 合优目录 1 介绍2 训练 1 介绍
本专题用来介绍使用最短路算法#xff08;spfa或dijkstra#xff09;与其它算法#xff08;dfs、二分、拓扑排序、动态规划等等#xff09;结合起来解题。
2 训练
题目1#xff1a;1135新年好
C代码如下#xff0c;
//版本1#xff0c;使… 目录 1 介绍2 训练 1 介绍
本专题用来介绍使用最短路算法spfa或dijkstra与其它算法dfs、二分、拓扑排序、动态规划等等结合起来解题。
2 训练
题目11135新年好
C代码如下
//版本1使用vector来存储图会有超时风险
#include iostream
#include cstring
#include algorithm
#include queue
#include vectorusing namespace std;const int N 50010;
int n, m;
int dist[6][N];
bool st[N];
vectorvectorpairint, int g; //使用vector可能有超时分险
int source[6];void spfa(int start, int dist[]) {memset(dist, 0x3f, N * 4);memset(st, 0, sizeof st);dist[start] 0;queueint q;q.push(start);st[start] true;while (!q.empty()) {auto t q.front();q.pop();st[t] false;for (auto [b, w] : g[t]) {if (dist[b] dist[t] w) {dist[b] dist[t] w;if (!st[b]) {q.push(b);st[b] true;}}}}return;
}int dfs(int u, int start, int distance) {if (u 5) return distance;int res 0x3f3f3f3f;for (int i 1; i 5; i) {if (!st[i]) {int b source[i];st[i] true;res min(res, dfs(u 1, i, distance dist[start][b]));st[i] false; }}return res;
}int main() {cin n m;g.resize(n 10);source[0] 1;for (int i 1; i 5; i) cin source[i];for (int i 0; i m; i) {int a, b, c;cin a b c;g[a].emplace_back(b, c);g[b].emplace_back(a, c);}for (int i 0; i 6; i) spfa(source[i], dist[i]);memset(st, 0, sizeof st);int res dfs(1, 0, 0);cout res endl;return 0;
}//版本2使用h,e,ne,w数组来存储图
#include cstdio
#include cstring
#include iostream
#include algorithm
#include queueusing namespace std;typedef pairint, int PII;const int N 50010, M 200010, INF 0x3f3f3f3f;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[6][N];
int source[6];
bool st[N];void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}void dijkstra(int start, int dist[]) {memset(dist, 0x3f, N * 4);dist[start] 0;memset(st, 0, sizeof st);priority_queuePII, vectorPII, greaterPII heap;heap.push({0, start});while (heap.size()) {auto t heap.top();heap.pop();int ver t.second;if (st[ver]) continue;st[ver] true;for (int i h[ver]; ~i; i ne[i]) {int j e[i];if (dist[j] dist[ver] w[i]) {dist[j] dist[ver] w[i];heap.push({dist[j], j});}}}
}int dfs(int u, int start, int distance) {if (u 5) return distance;int res INF;for (int i 1; i 5; i) {if (!st[i]) {int next source[i];st[i] true;res min(res, dfs(u 1, i, distance dist[start][next]));st[i] false; }}return res;
}int main() {scanf(%d%d, n, m);source[0] 1;for (int i 1; i 5; i) scanf(%d, source[i]);memset(h, -1, sizeof h);while (m--) {int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c), add(b, a, c);}for (int i 0; i 6; i) dijkstra(source[i], dist[i]);memset(st, 0, sizeof st);printf(%d\n, dfs(1, 0, 0));return 0;
}题目2340通信线路
C代码如下
#include iostream
#include cstring
#include algorithm
#include dequeusing namespace std;const int N 1010, M 20010;
int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
dequeint q;
bool st[N];void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}bool check(int bound) {memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);q.push_back(1);dist[1] 0;while (q.size()) {int t q.front();q.pop_front();if (st[t]) continue;st[t] true;for (int i h[t]; ~i; i ne[i]) {int j e[i], x w[i] bound;if (dist[j] dist[t] x) {dist[j] dist[t] x;if (!x) q.push_front(j);else q.push_back(j);}}}return dist[n] k;
}int main() {cin n m k;memset(h, -1, sizeof h);while (m--) {int a, b, c;cin a b c;add(a, b, c), add(b, a, c);}int l 0, r 1e6 1;while (l r) {int mid l r 1;if (check(mid)) r mid;else l mid 1;}if (r 1e6 1) cout -1 endl;else cout r endl;return 0;
}题目3342道路与航线
C代码如下
#include cstring
#include iostream
#include algorithm
#include vector
#include queue#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 25010, M 150010, INF 0x3f3f3f3f;
int n, mr, mp, S;
int id[N];
int h[N], e[M], w[M], ne[M], idx;
int dist[N], din[N];
vectorint block[N];
int bcnt;
bool st[N];
queueint q;void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}void dfs(int u, int bid) {id[u] bid, block[bid].push_back(u);for (int i h[u]; ~i; i ne[i]) {int j e[i];if (!id[j]) {dfs(j, bid);}}
}void dijkstra(int bid) {priority_queuePII, vectorPII, greaterPII heap;for (auto u : block[bid]) {heap.push({dist[u], u});}while (heap.size()) {auto t heap.top();heap.pop();int ver t.y, distance t.x;if (st[ver]) continue;st[ver] true;for (int i h[ver]; ~i; i ne[i]) {int j e[i];if (id[j] ! id[ver] --din[id[j]] 0) q.push(id[j]);if (dist[j] dist[ver] w[i]) {dist[j] dist[ver] w[i];if (id[j] id[ver]) heap.push({dist[j], j});}}}
}void topsort() {memset(dist, 0x3f, sizeof dist);dist[S] 0;for (int i 1; i bcnt; i) {if (!din[i]) {q.push(i);}}while (q.size()) {int t q.front();q.pop();dijkstra(t);}}int main() {cin n mr mp S;memset(h, -1, sizeof h);while (mr--) {int a, b, c;cin a b c;add(a, b, c), add(b, a, c);}for (int i 1; i n; i) {if (!id[i]) {bcnt;dfs(i, bcnt);}}while (mp--) {int a, b, c;cin a b c;din[id[b]];add(a, b, c);}topsort();for (int i 1; i n; i) {if (dist[i] INF / 2) cout NO PATH endl;else cout dist[i] endl;}return 0;
}题目4341最优贸易
C代码如下
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010, M 2000010;
int n, m;
int w[N];
int hs[N], ht[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
int q[N];
bool st[N];void add(int h[], int a, int b) {e[idx] b, ne[idx] h[a], h[a] idx;
}void spfa(int h[], int dist[], int type) {int hh 0, tt 1;if (type 0) {memset(dist, 0x3f, sizeof dmin);dist[1] w[1];q[0] 1;} else {memset(dist, -0x3f, sizeof dmax);dist[n] w[n];q[0] n;}while (hh ! tt) {int t q[hh];if (hh N) hh 0;st[t] false;for (int i h[t]; ~i; i ne[i]) {int j e[i];if (type 0 dist[j] min(dist[t], w[j]) || type 1 dist[j] max(dist[t], w[j])) {if (type 0) dist[j] min(dist[t], w[j]);else dist[j] max(dist[t], w[j]);if (!st[j]) {q[tt] j;if (tt N) tt 0;st[j] true;}}}}
}int main() {scanf(%d%d, n, m);for (int i 1; i n; i) scanf(%d, w[i]);memset(hs, -1, sizeof hs);memset(ht, -1, sizeof ht);while (m--) {int a, b, c;scanf(%d%d%d, a, b, c);add(hs, a, b), add(ht, b, a);if (c 2) add(hs, b, a), add(ht, a, b);}spfa(hs, dmin, 0);spfa(ht, dmax, 1);int res 0;for (int i 1; i n; i) res max(res, dmax[i] - dmin[i]);printf(%d\n, res);return 0;
}
