建设企业网站心得体会,莆田个人外贸网站建设,凡科网做网站,广州越秀区房价宣传一下算法提高课整理 —
CSDN个人主页#xff1a;更好的阅读体验 — 题目传送门点这里
题目描述
战争时期#xff0c;前线有 nnn 个哨所#xff0c;每个哨所可能会与其他若干个哨所之间有通信联系。
信使负责在哨所之间传递信息#xff0c;当然#xff0c;…宣传一下算法提高课整理 —
CSDN个人主页更好的阅读体验 — 题目传送门点这里
题目描述
战争时期前线有 nnn 个哨所每个哨所可能会与其他若干个哨所之间有通信联系。
信使负责在哨所之间传递信息当然这是要花费一定时间的以天为单位。
指挥部设在第一个哨所。
当指挥部下达一个命令后指挥部就派出若干个信使向与指挥部相连的哨所送信。
当一个哨所接到信后这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。
直至所有 nnn 个哨所全部接到命令后送信才算成功。
因为准备充足每个哨所内都安排了足够的信使如果一个哨所与其他 k 个哨所有通信联系的话这个哨所内至少会配备 kkk 个信使。
现在总指挥请你编一个程序计算出完成整个送信过程最短需要多少时间。
输入格式
第 111 行有两个整数 nnn 和 mmm中间用 111 个空格隔开分别表示有 nnn 个哨所和 mmm 条通信线路。
第 222 至 m1m1m1 行每行三个整数 i、j、ki、j、ki、j、k中间用 111 个空格隔开表示第 iii 个和第 jjj 个哨所之间存在 双向 通信线路且这条线路要花费 kkk 天。
输出格式
一个整数表示完成整个送信过程的最短时间。
如果不是所有的哨所都能收到信就输出-1。
数据范围
1≤n≤100,1≤n≤100,1≤n≤100, 1≤m≤200,1≤m≤200,1≤m≤200, 1≤k≤10001≤k≤10001≤k≤1000
样例输入
4 4
1 2 4
2 3 7
2 4 1
3 4 6样例输出
11题目化简
给定一个 nnn 个点 mmm 条边的无向图求编号为1的点与其他点之间最短距离的最大值。
思路
这道题因为数据范围极小为了节约代码长度可以采用Floyd算法。
在求出任意两点间最短距离之后遍历dist[1][i]求出最大值。
Dijkstra算法与Floyd类似代码部分也给出了朴素Dijkstra和堆优化Dijkstra的代码。
算法时间复杂度
如果采用Floyd算法那么时间复杂度是O(n3)O(n^3)O(n3)
朴素Dijkstra算法O(n2)O(n^2)O(n2), 但是代码较长
堆优化Dijkstra算法O(mlogn)O(m \log n)O(mlogn)同样的代码较长
AC Code C(Floyd)C (Floyd)C(Floyd) #include iostream
#include cstring
#include algorithmusing namespace std;const int N 110, inf 1e9;int n, m;
int d[N][N];void init()
{for (int i 1; i n; i )for (int j 1; j n; j )if (i j) d[i][j] 0;else d[i][j] inf;
}void floyd()
{for (int k 1; k n; k )for (int i 1; i n; i )for (int j 1; j n; j )d[i][j] min(d[i][j], d[i][k] d[k][j]);
}int main()
{cin n m;init();while (m -- ){int a, b, c;cin a b c;d[a][b] min(d[a][b], c);d[b][a] min(d[b][a], c);}floyd();int res 0;for (int i 2; i n; i )res max(res, d[1][i]);if (res inf) puts(-1);else printf(%d\n, res);return 0;
}C(朴素Dijkstra)C (朴素Dijkstra)C(朴素Dijkstra) #include iostream
#include cstring
#include algorithmusing namespace std;const int N 110;int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstra()
{int res 0;memset(dist, 0x3f, sizeof dist);dist[1] 0;for (int i 1; i n; i ){int t -1;for (int j 1; j n; j )if (!st[j] (t -1 || dist[t] dist[j]))t j;st[t] true;res max(res, dist[t]);for (int j 1; j n; j )dist[j] min(dist[j], dist[t] g[t][j]);}return res 0x3f3f3f3f ? -1 : res;
}
int main()
{memset(g, 0x3f, sizeof g);scanf(%d%d, n, m);while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);g[a][b] g[b][a] min(g[a][b], c);}cout dijkstra() endl;return 0;
}C(堆优化Dijkstra)C (堆优化Dijkstra)C(堆优化Dijkstra) #include iostream
#include cstring
#include algorithm
#include queue#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 110, M N 2;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}
int dijkstra()
{int res 0, cnt 0;memset(dist, 0x3f, sizeof dist);dist[1] 0;priority_queuePII, vectorPII, greater heap;heap.push({0, 1});while (!heap.empty()){PII u heap.top();heap.pop();if (st[u.y]) continue;st[u.y] true;res max(res, u.x);cnt ;for (int i h[u.y]; ~i; i ne[i]){int j e[i];if (dist[j] dist[u.y] w[i]){dist[j] dist[u.y] w[i];heap.push({dist[j], j});}}}return cnt n ? res : -1;
}
int main()
{memset(h, -1, sizeof h);scanf(%d%d, n, m);while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c), add(b, a, c);}cout dijkstra() endl;return 0;
}最后如果觉得对您有帮助的话点个赞再走吧
