深圳做网站 创同盟,最新新闻,平面设计要什么学历,优秀的电商app设计网站目录 1.网络延迟时间
弗洛伊德算法
迪杰斯特拉算法
2. K 站中转内最便宜的航班
3.从第一个节点出发到最后一个节点的受限路径数
4.到达目的地的方案数 1.网络延迟时间
有 n 个网络节点#xff0c;标记为 1 到 n。
给你一个列表 times#xff0c;表示信号经过 有向 边的…目录 1.网络延迟时间
弗洛伊德算法
迪杰斯特拉算法
2. K 站中转内最便宜的航班
3.从第一个节点出发到最后一个节点的受限路径数
4.到达目的地的方案数 1.网络延迟时间
有 n 个网络节点标记为 1 到 n。
给你一个列表 times表示信号经过 有向 边的传递时间。 times[i] (ui, vi, wi)其中 ui 是源节点vi 是目标节点 wi 是一个信号从源节点传递到目标节点的时间。
现在从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号如果不能使所有节点收到信号返回 -1 。
示例 1 输入times [[2,1,1],[2,3,1],[3,4,1]], n 4, k 2
输出2示例 2
输入times [[1,2,1]], n 2, k 1
输出1示例 3
输入times [[1,2,1]], n 2, k 2
输出-1提示
1 k n 1001 times.length 6000times[i].length 31 ui, vi nui ! vi0 wi 100所有 (ui, vi) 对都 互不相同即不含重复边
分析要求最快能到达所有点就是要找到这个点到达所有点的最短路径的最大值用弗洛伊德算法的话就是比较暴力了算出来所有的以后在需要的顶点找最大值但是迪杰斯特拉算法少一层循环只要这个顶点到记录到所有顶点的最小距离就好
弗洛伊德算法用邻接矩阵的时候可以直接在邻接矩阵上操作不用再利用结构体去建图
弗洛伊德算法
分析要更新邻接矩阵需要一个中间点写在三层循环的最外层 #include bits/stdc.h
using namespace std;
main()
{//接受数据int arc,n;cinnarc;int i,j,s[n][n];for(i0; in; i)for(j0; jn; j){if(j!i) s[i][j]99999;else s[i][j]0;}int a,b,c;for(i0; iarc; i){cinabc;s[a-1][b-1]c;}cina;aa-1;//三层循环for(b0; bn; b){for(i0; in; i){for(j0; jn; j)s[i][j]min(s[i][j],s[i][b]s[b][j]);}}int ans0;for(i0; in; i)ansmax(ans,s[a][i]);
// for(i0; in; i)
// {
// for(j0; jn; j)
// couts[i][j] ;
// coutendl;
// }ansans9999?-1:ans;coutans;}迪杰斯特拉算法
分析找到了一个讲迪杰斯特拉算法的文章讲的挺详细的【C】Dijkstra算法_dijkstra c-CSDN博客
先从邻接矩阵开始写要设置好visit[]做标记和dist[]记录最短距离从0开始循环n遍保证每个点都可以做一次中间点找到最短的且未被标记的然后以她作为中间点更新 #include bits/stdc.h
using namespace std;
main()
{//接收数据int arc,n;cinnarc;int i,j,k,s[n][n];for(i0; in; i)for(j0; jn; j){if(j!i) s[i][j]99999;else s[i][j]0;}int a,b,c;for(i0; iarc; i){cinabc;s[a-1][b-1]c;}for(i0; in; i){for(j0; jn; j){couts[i][j] ;}coutendl;}cina;//迪杰斯特拉int visit[n],dist[n];memset(visit,0,sizeof(visit));memset(dist,9999,sizeof(dist));dist[a-1]0;dist[-1]9999;//循环n遍for(i0; in; i){j-1;//计算最小for(k0; kn; k){if(!visit[k]dist[k]dist[j])jk;}//做标记visit[j]1;//更新路径for(k0; kn; k){dist[k]min(dist[k],dist[j]s[j][k]);}for(k0;kn;k) coutdist[k] ;coutendl;}int ans0;for(i0; in; i){ansmax(ans,dist[i]);}ansans9999?-1:ans;coutans;}2. K 站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights 其中 flights[i] [fromi, toi, pricei] 表示该航班都从城市 fromi 开始以价格 pricei 抵达 toi。
现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到出一条最多经过 k 站中转的路线使得从 src 到 dst 的 价格最便宜 并返回该价格。 如果不存在这样的路线则输出 -1。 示例 1
输入:
n 3, edges [[0,1,100],[1,2,100],[0,2,500]]
src 0, dst 2, k 1
输出: 200
解释:
城市航班图如下
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200如图中红色所示。
示例 2
输入:
n 3, edges [[0,1,100],[1,2,100],[0,2,500]]
src 0, dst 2, k 0
输出: 500
解释:
城市航班图如下
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500如图中蓝色所示。提示
1 n 1000 flights.length (n * (n - 1) / 2)flights[i].length 30 fromi, toi nfromi ! toi1 pricei 104航班没有重复且不存在自环0 src, dst, k nsrc ! dst
分析我想到的时用迪杰斯特拉算法在计算的过程中记录中转次数进行剪枝,比较容易出错的点就是可以中专k次但是直接到达的算是中转0次但是如果是原点和终点在同一个地方的话要比0次少一次那就是-1次但是我设置的是从原点到原点是0次所以可以理解成到达某个地方需要乘坐几次航班那就是乘坐k1次时才算中转k次这里比较容易出错 #include bits/stdc.h
using namespace std;
main()
{int arc,n;cinnarc;int i,j,k,s[n][n];for(i0; in; i)for(j0; jn; j){if(j!i) s[i][j]99999;else s[i][j]0;}int a,b,c;for(i0; iarc; i){cinabc;s[a][b]c;}
// for(i0; in; i)
// {
// for(j0; jn; j)
// {
// couts[i][j] ;
// }
// coutendl;
// }cinabc;int visit[n],dist[n],ans[n];memset(visit,0,sizeof(visit));memset(dist,9999,sizeof(dist));memset(ans,0,sizeof(ans));dist[a]0;dist[-1]9999;for(i0;in;i){j-1;for(k0;kn;k){if(!visit[k]dist[k]dist[j]) jk;}visit[j]1;for(k0;kn;k){if(dist[k]dist[j]s[j][k] ans[j]1c1){ans[k]ans[j]1;dist[k]dist[j]s[j][k];}}}// for(i0;in;i) coutans[i] ;coutdist[b];
}3.从第一个节点出发到最后一个节点的受限路径数
现有一个加权无向连通图。给你一个正整数 n 表示图中有 n 个节点并按从 1 到 n 给节点编号另给你一个数组 edges 其中每个 edges[i] [ui, vi, weighti] 表示存在一条位于节点 ui 和 vi 之间的边这条边的权重为 weighti 。
从节点 start 出发到节点 end 的路径是一个形如 [z0, z1, z2, ..., zk] 的节点序列满足 z0 start 、zk end 且在所有符合 0 i k-1 的节点 zi 和 zi1 之间存在一条边。
路径的距离定义为这条路径上所有边的权重总和。用 distanceToLastNode(x) 表示节点 n 和 x 之间路径的最短距离。受限路径 为满足 distanceToLastNode(zi) distanceToLastNode(zi1) 的一条路径其中 0 i k-1 。
返回从节点 1 出发到节点 n 的 受限路径数 。由于数字可能很大请返回对 109 7 取余 的结果。
示例 1 输入n 5, edges [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
输出3
解释每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。三条受限路径分别是
1) 1 -- 2 -- 5
2) 1 -- 2 -- 3 -- 5
3) 1 -- 3 -- 5示例 2 输入n 7, edges [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
输出1
解释每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。唯一一条受限路径是1 -- 3 -- 7 。提示
1 n 2 * 104n - 1 edges.length 4 * 104edges[i].length 31 ui, vi nui ! vi1 weighti 105任意两个节点之间至多存在一条边任意两个节点之间至少存在一条路径
分析这个是要先算出各个点到n点的最短路径这个的话就应该是迪杰斯特拉算法了然后放在dist[]中记录然后就要搜索所有的路径根据dist[]的要求去剪枝这种搜索的话我想到的是回溯如果这条路可以走的话进行剪枝但是我看题解好像更多人用的是动态规划 直接用dp[]表示1到i的受限路径数这样会简单很多这样放一起来想的话回溯更适合那种要求写出路径的像这种只求路径数的更适合动态规划 #include bits/stdc.h
using namespace std;
main()
{int arc,n;cinnarc;int i,j,k,s[n][n];for(i0; in; i)for(j0; jn; j){if(j!i) s[i][j]9999;else s[i][j]0;}int a,b,c;for(i0; iarc; i){cinabc;s[a-1][b-1]c;s[b-1][a-1]c;}
// for(i0; in; i)
// {
// for(j0; jn; j)
// {
// couts[i][j] ;
// }
// coutendl;
// }int visit[n],dist[n],dp[n];memset(visit,0,sizeof(visit));memset(dist,9999,sizeof(dist));memset(dp,0,sizeof(dp));dist[n-1]0;dist[-1]9999;for(i0;in;i){j-1;for(k0;kn;k){if(!visit[k]dist[k]dist[j]) jk;}visit[j]1;for(k0;kn;k){dist[k]min(dist[k],dist[j]s[j][k]);}}
// for(i0;in;i) coutdist[i] ;coutendl;dp[0]1;for(i0;in;i){for(ji1;jn;j){if(s[i][j]!9999 dist[i]dist[j])dp[j]dp[j]dp[i];}for(k0;kn;k) coutdp[k] ;coutendl;}
// for(i0;in;i) coutdp[i] ;coutendl;coutdp[n-1];
//7 8
//1 3 1
//4 1 2
//7 3 4
//2 5 3
//5 6 1
//6 7 2
//7 5 3
//2 6 4}4.到达目的地的方案数
你在一个城市里城市由 n 个路口组成路口编号为 0 到 n - 1 某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口且任意两个路口之间最多有一条路。
给你一个整数 n 和二维整数数组 roads 其中 roads[i] [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大将结果对 109 7 取余 后返回。
示例 1 输入n 7, roads [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
输出4
解释从路口 0 出发到路口 6 花费的最少时间是 7 分钟。
四条花费 7 分钟的路径分别为
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6示例 2
输入n 2, roads [[1,0,10]]
输出1
解释只有一条从路口 0 到路口 1 的路花费 10 分钟。提示
1 n 200n - 1 roads.length n * (n - 1) / 2roads[i].length 30 ui, vi n - 11 timei 109ui ! vi任意两个路口之间至多有一条路。从任意路口出发你能够到达其他任意路口。
分析我刚开始只想到了要用迪杰斯特拉算法计算出最小路径然后再用动态规划计算路径数目但是到计算路径数目的时候被难到了总想着要用回溯去找路径后来看了别人的题解才的发现有一个性质是如果是合法路径那么在途中经过的每一个点都是以最短路径的方式到达的也就是说走到这里消费的时间其实就是dist[i]
那么就可以用dp[i]记录走到这里等于dist[i]的数目然后更新dp[i]
#include bits/stdc.h
using namespace std;
main()
{int arc,n;cinnarc;int i,j,k,s[n][n];for(i0; in; i)for(j0; jn; j){if(j!i) s[i][j]9999;else s[i][j]0;}int a,b,c;for(i0; iarc; i){cinabc;s[a][b]c;s[b][a]c;}
// for(i0; in; i)
// {
// for(j0; jn; j)
// {
// couts[i][j] ;
// }
// coutendl;
// }int visit[n],dist[n],dp[n];memset(visit,0,sizeof(visit));memset(dist,9999,sizeof(dist));memset(dp,0,sizeof(dp));dist[0]0;dist[-1]9999;for(i0;in;i){j-1;for(k0;kn;k){if(!visit[k]dist[k]dist[j]) jk;}visit[j]1;for(k0;kn;k){dist[k]min(dist[k],dist[j]s[j][k]);}}
// for(i0;in;i) coutdist[i] ;coutendl;dp[0]1;for(i0;in;i){for(ji1;jn;j){if(s[i][j]!9999 dist[j]dist[i]s[i][j])dp[j]dp[j]dp[i];}
// for(k0;kn;k) coutdp[k] ;
// coutendl;}
// for(i0;in;i) coutdp[i] ;coutendl;coutdp[n-1];
//7 10
//0 6 7
//0 1 2
//1 2 3
//1 3 3
//6 3 3
//3 5 1
//6 5 1
//2 5 1
//0 4 5
//4 6 2}
