网站开发的背景意义,群辉wordpress语言,龙岗seo培训,中国空间站vr全景目录 1 介绍2 训练 1 介绍
本博客用来记录使用dijkstra算法或spfa算法求解最短路问题的题目。
2 训练
题目1#xff1a;1129热浪
C代码如下#xff0c;
#include iostream
#include cstring
#include algorithm
#include vector
#inclu… 目录 1 介绍2 训练 1 介绍
本博客用来记录使用dijkstra算法或spfa算法求解最短路问题的题目。
2 训练
题目11129热浪
C代码如下
#include iostream
#include cstring
#include algorithm
#include vector
#include queueusing namespace std;const int N 2510;
int n, m;
vectorvectorpairint,int g; //first表示next_nodesecond表示w
int dist[N];
bool st[N];
int snode, enode;void dijkstra() {memset(dist, 0x3f, sizeof dist);dist[snode] 0;priority_queuepairint, int, vectorpairint,int, greaterpairint,int h;h.push(make_pair(0, snode));while (!h.empty()) {//确定当前结点中不在集合s且距离结点snode最近的结点。记作cnodeauto t h.top();h.pop();int cdist t.first, cnode t.second;if (st[cnode]) continue; //如果cnode已经被确定是最小路径上的结点了则跳过st[cnode] true; //将它加入到集合中for (auto [next_node, w] : g[cnode]) {if (dist[next_node] cdist w) {dist[next_node] cdist w;h.push(make_pair(dist[next_node], next_node));}}}return;
}int main() {cin n m snode enode;g.resize(n 10);for (int i 1; i m; i) {int a, b, c;cin a b c;g[a].emplace_back(b, c);g[b].emplace_back(a, c);}//求snode到enode的最短距离dijkstra();cout dist[enode] endl;return 0;
}题目21128信使
C代码如下
#include iostream
#include cstring
#include algorithm
#include vector
#include queueusing namespace std;const int N 110;
int n, m;
int d[N];
bool st[N];
vectorvectorpairint,int g;void dijkstra() {memset(d, 0x3f, sizeof d);d[1] 0;priority_queuepairint,int, vectorpairint,int, greaterpairint,int hp; //小根堆hp.push(make_pair(0, 1)); //first表示距离second表示结点while (!hp.empty()) {auto t hp.top(); //找到未在集合中距离最小的结点hp.pop();int a t.second;if (st[a]) continue; //已经用d[a]更新过了将它放入集合中st[a] true;for (auto [b, w] : g[a]) {if (d[b] d[a] w) { //d[b]此时比较大用一个更小值来更新它。d[b] d[a] w;hp.push(make_pair(d[b], b));}}}return;
}int main() {cin n m;g.resize(n 10);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);}dijkstra();int res 0; //求最大值for (int i 1; i n; i) res max(res, d[i]);if (res 0x3f3f3f3f) {res -1;}cout res endl;return 0;
}题目31127香甜的黄油
C代码如下
#include iostream
#include cstring
#include algorithm
#include climits
#include vector
#include queueusing namespace std;const int N 810;
int cow, n, m;
int cnt[N];
int d[N];
bool st[N];
vectorvectorpairint,int g;void spfa(int start) {//起点为startmemset(d, 0x3f, sizeof d);memset(st, 0, sizeof st);d[start] 0;queueint q;q.push(start);st[start] true; //结点start在队列中while (!q.empty()) {int t q.front();q.pop();st[t] false; //结点t不在队列中了for (auto [b, w] : g[t]) {if (d[b] d[t] w) {d[b] d[t] w;if (!st[b]) {q.push(b);st[b] true;}}}}return;
}int main() {cin cow n m;g.resize(n 10);for (int i 1; i cow; i) {int a;cin a; //每头牛所在的牧场cnt[a];}for (int i 1; i m; i) {int a, b, c;cin a b c;g[a].emplace_back(b, c);g[b].emplace_back(a, c);}//spfa()算法 //o(m)时间复杂度不会被超时long long res INT_MAX;for (int i 1; i n; i) {//第i个牧场作为放糖点spfa(i);long long t 0; for (int j 1; j n; j) t cnt[j] * d[j];res min(res, t);}cout res endl;return 0;
}题目41126最小花费
#include iostream
#include cstring
#include algorithm
#include queue
#include vectorusing namespace std;const int N 2010;
int n, m;
int snode, enode;
double d[N]; //求最大距离最大利率
bool st[N]; //是否使用它来更新过
vectorvectorpairint,int g;void dijkstra() {//d的初始化for (int i 1; i n; i) d[i] 0.0; //初始成0.0memset(st, 0, sizeof st);d[snode] 1.0;priority_queuepairdouble,int hp; //大根堆hp.push(make_pair(1.0, snode));while (!hp.empty()) {auto t hp.top();hp.pop();int a t.second;if (st[a]) continue;st[a] true;for (auto [b, w] : g[a]) {if (d[b] d[a] * 0.01 * (100 - w)) {d[b] d[a] * 0.01 * (100 - w);hp.push(make_pair(d[b], b));}}}return;
}int main() {cin n m;g.resize(n 10);for (int i 1; i m; i) {int a, b, c;cin a b c;g[a].emplace_back(b, c);g[b].emplace_back(a, c);}cin snode enode;dijkstra();double res 100.0 / d[enode];printf(%.8f\n, res);return 0;
}题目5920最优乘车
C代码如下
#include iostream
#include cstring
#include algorithm
#include sstream
#include vector
#include queueusing namespace std;const int N 510;
int n, m;
vectorvectorint g;
bool st[N];
int dist[N];void bfs() {memset(dist, 0x3f, sizeof dist);queueint q;q.push(1);dist[1] 0;st[1] true;while (!q.empty()) {auto t q.front();q.pop();//t可以走到哪儿for (auto b : g[t]) {if (!st[b]) {dist[b] dist[t] 1;q.push(b);st[b] true;}}}return;
}int main() {cin m n;g.resize(n 10);string line;getline(cin, line);for (int i 0; i m; i) {getline(cin, line);stringstream ssin(line);vectorint nodes;int node -1;while (ssin node) {nodes.emplace_back(node);}for (int i 0; i nodes.size(); i) {for (int j i 1; j nodes.size(); j) {g[nodes[i]].emplace_back(nodes[j]);}}}bfs();if (dist[n] 0x3f3f3f3f) puts(NO);else cout max(dist[n] - 1, 0) endl;return 0;
}题目6903昂贵的聘礼
C代码如下
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 110, INF 0x3f3f3f3f;
int n, m;
int w[N][N], level[N];
int dist[N];
bool st[N];int dijkstra(int down, int up) {memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[0] 0;for (int i 1; i n 1; i) {int t -1;for (int j 0; j n; j) {if (!st[j] (t -1 || dist[t] dist[j])) {t j;}}st[t] true;for (int j 1; j n; j) {if (level[j] down level[j] up) {dist[j] min(dist[j], dist[t] w[t][j]);}}}return dist[1];
}int main() {cin m n;memset(w, 0x3f, sizeof w);for (int i 1; i n; i) w[i][i] 0;for (int i 1; i n; i) {int price, cnt;cin price level[i] cnt;w[0][i] min(price, w[0][i]);while (cnt--) {int id, cost;cin id cost;w[id][i] min(w[id][i], cost);}}int res INF;for (int i level[1] - m; i level[1]; i) res min(res, dijkstra(i, i m));cout res endl;return 0;
}
