目錄
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 <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
- 所有?
(ui, vi)
?對都?互不相同(即,不含重復邊)
分析:要求最快能到達所有點,就是要找到這個點到達所有點的最短路徑的最大值,用弗洛伊德算法的話就是比較暴力了,算出來所有的以后在需要的頂點找最大值,但是迪杰斯特拉算法少一層循環,只要這個頂點到記錄到所有頂點的最小距離就好?
弗洛伊德算法用鄰接矩陣的時候,可以直接在鄰接矩陣上操作,不用再利用結構體去建圖
弗洛伊德算法
分析:要更新鄰接矩陣,需要一個中間點,寫在三層循環的最外層
#include <bits/stdc++.h>
using namespace std;
main()
{//接受數據int arc,n;cin>>n>>arc;int i,j,s[n][n];for(i=0; i<n; i++)for(j=0; j<n; j++){if(j!=i) s[i][j]=99999;else s[i][j]=0;}int a,b,c;for(i=0; i<arc; i++){cin>>a>>b>>c;s[a-1][b-1]=c;}cin>>a;a=a-1;//三層循環for(b=0; b<n; b++){for(i=0; i<n; i++){for(j=0; j<n; j++)s[i][j]=min(s[i][j],s[i][b]+s[b][j]);}}int ans=0;for(i=0; i<n; i++)ans=max(ans,s[a][i]);
// for(i=0; i<n; i++)
// {
// for(j=0; j<n; j++)
// cout<<s[i][j]<<" ";
// cout<<endl;
// }ans=ans>9999?-1:ans;cout<<ans;}
迪杰斯特拉算法
分析:找到了一個講迪杰斯特拉算法的文章,講的挺詳細的【C++】Dijkstra算法_dijkstra c++-CSDN博客
先從鄰接矩陣開始寫,要設置好visit[](做標記)和dist[](記錄最短距離),從0開始循環n遍,保證每個點都可以做一次中間點,找到最短的且未被標記的,然后以她作為中間點更新
#include <bits/stdc++.h>
using namespace std;
main()
{//接收數據int arc,n;cin>>n>>arc;int i,j,k,s[n][n];for(i=0; i<n; i++)for(j=0; j<n; j++){if(j!=i) s[i][j]=99999;else s[i][j]=0;}int a,b,c;for(i=0; i<arc; i++){cin>>a>>b>>c;s[a-1][b-1]=c;}for(i=0; i<n; i++){for(j=0; j<n; j++){cout<<s[i][j]<<" ";}cout<<endl;}cin>>a;//迪杰斯特拉int visit[n],dist[n];memset(visit,0,sizeof(visit));memset(dist,9999,sizeof(dist));dist[a-1]=0;dist[-1]=9999;//循環n遍for(i=0; i<n; i++){j=-1;//計算最小for(k=0; k<n; k++){if(!visit[k]&&dist[k]<=dist[j])j=k;}//做標記visit[j]=1;//更新路徑for(k=0; k<n; k++){dist[k]=min(dist[k],dist[j]+s[j][k]);}for(k=0;k<n;k++) cout<<dist[k]<<" ";cout<<endl;}int ans=0;for(i=0; i<n; i++){ans=max(ans,dist[i]);}ans=ans>9999?-1:ans;cout<<ans;}
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 <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 104
- 航班沒有重復,且不存在自環
0 <= src, dst, k < n
src != dst
分析:我想到的時用迪杰斯特拉算法,在計算的過程中記錄中轉次數進行剪枝,比較容易出錯的點就是可以中專k次,但是直接到達的算是中轉0次,但是如果是原點和終點在同一個地方的話要比0次少一次,那就是-1次,但是我設置的是從原點到原點是0次,所以可以理解成到達某個地方需要乘坐幾次航班,那就是乘坐k+1次時才算中轉k次,這里比較容易出錯
#include <bits/stdc++.h>
using namespace std;
main()
{int arc,n;cin>>n>>arc;int i,j,k,s[n][n];for(i=0; i<n; i++)for(j=0; j<n; j++){if(j!=i) s[i][j]=99999;else s[i][j]=0;}int a,b,c;for(i=0; i<arc; i++){cin>>a>>b>>c;s[a][b]=c;}
// for(i=0; i<n; i++)
// {
// for(j=0; j<n; j++)
// {
// cout<<s[i][j]<<" ";
// }
// cout<<endl;
// }cin>>a>>b>>c;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(i=0;i<n;i++){j=-1;for(k=0;k<n;k++){if(!visit[k]&&dist[k]<=dist[j]) j=k;}visit[j]=1;for(k=0;k<n;k++){if(dist[k]>dist[j]+s[j][k] && ans[j]+1<=c+1){ans[k]=ans[j]+1;dist[k]=dist[j]+s[j][k];}}}// for(i=0;i<n;i++) cout<<ans[i]<<" ";cout<<dist[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
?和?zi+1
?之間存在一條邊。
路徑的距離定義為這條路徑上所有邊的權重總和。用?distanceToLastNode(x)
?表示節點?n
?和?x
?之間路徑的最短距離。受限路徑?為滿足?distanceToLastNode(zi) > distanceToLastNode(zi+1)
?的一條路徑,其中?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 * 104
n - 1 <= edges.length <= 4 * 104
edges[i].length == 3
1 <= ui, vi <= n
ui != vi
1 <= weighti <= 105
- 任意兩個節點之間至多存在一條邊
- 任意兩個節點之間至少存在一條路徑
分析:這個是要先算出各個點到n點的最短路徑,這個的話就應該是迪杰斯特拉算法了,然后放在dist[]中記錄,然后就要搜索所有的路徑根據dist[]的要求去剪枝,這種搜索的話我想到的是回溯,如果這條路可以走的話進行剪枝,但是我看題解好像更多人用的是動態規劃?,直接用dp[]表示1到i的受限路徑數,這樣會簡單很多,這樣放一起來想的話,回溯更適合那種要求寫出路徑的,像這種只求路徑數的更適合動態規劃
#include <bits/stdc++.h>
using namespace std;
main()
{int arc,n;cin>>n>>arc;int i,j,k,s[n][n];for(i=0; i<n; i++)for(j=0; j<n; j++){if(j!=i) s[i][j]=9999;else s[i][j]=0;}int a,b,c;for(i=0; i<arc; i++){cin>>a>>b>>c;s[a-1][b-1]=c;s[b-1][a-1]=c;}
// for(i=0; i<n; i++)
// {
// for(j=0; j<n; j++)
// {
// cout<<s[i][j]<<" ";
// }
// cout<<endl;
// }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(i=0;i<n;i++){j=-1;for(k=0;k<n;k++){if(!visit[k]&&dist[k]<=dist[j]) j=k;}visit[j]=1;for(k=0;k<n;k++){dist[k]=min(dist[k],dist[j]+s[j][k]);}}
// for(i=0;i<n;i++) cout<<dist[i]<<" ";cout<<endl;dp[0]=1;for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(s[i][j]!=9999 && dist[i]>dist[j])dp[j]=dp[j]+dp[i];}for(k=0;k<n;k++) cout<<dp[k]<<" ";cout<<endl;}
// for(i=0;i<n;i++) cout<<dp[i]<<" ";cout<<endl;cout<<dp[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 <= 200
n - 1 <= roads.length <= n * (n - 1) / 2
roads[i].length == 3
0 <= ui, vi <= n - 1
1 <= timei <= 109
ui != vi
- 任意兩個路口之間至多有一條路。
- 從任意路口出發,你能夠到達其他任意路口。
分析:我剛開始只想到了要用迪杰斯特拉算法計算出最小路徑,然后再用動態規劃計算路徑數目,但是到計算路徑數目的時候被難到了,總想著要用回溯去找路徑,后來看了別人的題解才的發現有一個性質是:如果是合法路徑,那么在途中經過的每一個點都是以最短路徑的方式到達的,也就是說,走到這里消費的時間其實就是dist[i]
那么就可以用dp[i]記錄走到這里等于dist[i]的數目,然后更新dp[i]
#include <bits/stdc++.h>
using namespace std;
main()
{int arc,n;cin>>n>>arc;int i,j,k,s[n][n];for(i=0; i<n; i++)for(j=0; j<n; j++){if(j!=i) s[i][j]=9999;else s[i][j]=0;}int a,b,c;for(i=0; i<arc; i++){cin>>a>>b>>c;s[a][b]=c;s[b][a]=c;}
// for(i=0; i<n; i++)
// {
// for(j=0; j<n; j++)
// {
// cout<<s[i][j]<<" ";
// }
// cout<<endl;
// }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(i=0;i<n;i++){j=-1;for(k=0;k<n;k++){if(!visit[k]&&dist[k]<=dist[j]) j=k;}visit[j]=1;for(k=0;k<n;k++){dist[k]=min(dist[k],dist[j]+s[j][k]);}}
// for(i=0;i<n;i++) cout<<dist[i]<<" ";cout<<endl;dp[0]=1;for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(s[i][j]!=9999 && dist[j]==dist[i]+s[i][j])dp[j]=dp[j]+dp[i];}
// for(k=0;k<n;k++) cout<<dp[k]<<" ";
// cout<<endl;}
// for(i=0;i<n;i++) cout<<dp[i]<<" ";cout<<endl;cout<<dp[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}