做公司網(wǎng)站的服務(wù)費入什么費用seo搜論壇
目錄
1.網(wǎng)絡(luò)延遲時間
弗洛伊德算法
迪杰斯特拉算法
2.?K 站中轉(zhuǎn)內(nèi)最便宜的航班
3.從第一個節(jié)點出發(fā)到最后一個節(jié)點的受限路徑數(shù)
4.到達目的地的方案數(shù)
1.網(wǎng)絡(luò)延遲時間
有?n?個網(wǎng)絡(luò)節(jié)點，標記為?1?到?n。
給你一個列表?times，表示信號經(jīng)過?有向?邊的傳遞時間。?times[i] = (ui, vi, wi)，其中?ui?是源節(jié)點，vi?是目標節(jié)點，?wi?是一個信號從源節(jié)點傳遞到目標節(jié)點的時間。
現(xiàn)在，從某個節(jié)點?K?發(fā)出一個信號。需要多久才能使所有節(jié)點都收到信號？如果不能使所有節(jié)點收到信號，返回?-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)?對都?互不相同（即，不含重復(fù)邊）
分析：要求最快能到達所有點，就是要找到這個點到達所有點的最短路徑的最大值，用弗洛伊德算法的話就是比較暴力了，算出來所有的以后在需要的頂點找最大值，但是迪杰斯特拉算法少一層循環(huán)，只要這個頂點到記錄到所有頂點的最小距離就好?
弗洛伊德算法用鄰接矩陣的時候，可以直接在鄰接矩陣上操作，不用再利用結(jié)構(gòu)體去建圖
弗洛伊德算法
分析：要更新鄰接矩陣，需要一個中間點，寫在三層循環(huán)的最外層
#include <bits/stdc++.h>
using namespace std;
main()
{//接受數(shù)據(jù)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;//三層循環(huán)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博客
先從鄰接矩陣開始寫，要設(shè)置好visit[]（做標記）和dist[]（記錄最短距離），從0開始循環(huán)n遍，保證每個點都可以做一次中間點，找到最短的且未被標記的，然后以她作為中間點更新
#include <bits/stdc++.h>
using namespace std;
main()
{//接收數(shù)據(jù)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;//循環(huán)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 站中轉(zhuǎn)內(nèi)最便宜的航班
有?n?個城市通過一些航班連接。給你一個數(shù)組?flights?，其中?flights[i] = [fromi, toi, pricei]?，表示該航班都從城市?fromi?開始，以價格?pricei?抵達?toi。
現(xiàn)在給定所有的城市和航班，以及出發(fā)城市?src?和目的地?dst，你的任務(wù)是找到出一條最多經(jīng)過?k?站中轉(zhuǎn)的路線，使得從?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 站中轉(zhuǎn)以內(nèi)的最便宜價格是 200，如圖中紅色所示。
示例 2：
輸入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 輸出: 500 解釋: 城市航班圖如下 ?從城市 0 到城市 2 在 0 站中轉(zhuǎn)以內(nèi)的最便宜價格是 500，如圖中藍色所示。
提示：
1 <= n <= 1000 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= fromi, toi < nfromi != toi1 <= pricei <= 104- 航班沒有重復(fù)，且不存在自環(huán)
0 <= src, dst, k < nsrc != dst
分析：我想到的時用迪杰斯特拉算法，在計算的過程中記錄中轉(zhuǎn)次數(shù)進行剪枝,比較容易出錯的點就是可以中專k次，但是直接到達的算是中轉(zhuǎn)0次，但是如果是原點和終點在同一個地方的話要比0次少一次，那就是-1次，但是我設(shè)置的是從原點到原點是0次，所以可以理解成到達某個地方需要乘坐幾次航班，那就是乘坐k+1次時才算中轉(zhuǎn)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.從第一個節(jié)點出發(fā)到最后一個節(jié)點的受限路徑數(shù)
現(xiàn)有一個加權(quán)無向連通圖。給你一個正整數(shù)?n?，表示圖中有?n?個節(jié)點，并按從?1?到?n?給節(jié)點編號；另給你一個數(shù)組?edges?，其中每個?edges[i] = [ui, vi, weighti]?表示存在一條位于節(jié)點?ui?和?vi?之間的邊，這條邊的權(quán)重為?weighti?。
從節(jié)點?start?出發(fā)到節(jié)點?end?的路徑是一個形如?[z0, z1, z2, ..., zk]?的節(jié)點序列，滿足?z0 = start?、zk = end?且在所有符合?0 <= i <= k-1?的節(jié)點?zi?和?zi+1?之間存在一條邊。
路徑的距離定義為這條路徑上所有邊的權(quán)重總和。用?distanceToLastNode(x)?表示節(jié)點?n?和?x?之間路徑的最短距離。受限路徑?為滿足?distanceToLastNode(zi) > distanceToLastNode(zi+1)?的一條路徑，其中?0 <= i <= k-1?。
返回從節(jié)點?1?出發(fā)到節(jié)點?n?的?受限路徑數(shù)?。由于數(shù)字可能很大，請返回對?109 + 7?取余?的結(jié)果。
示例 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 解釋：每個圓包含黑色的節(jié)點編號和藍色的 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 解釋：每個圓包含黑色的節(jié)點編號和藍色的 distanceToLastNode 值。唯一一條受限路徑是：1 --> 3 --> 7 。
提示：
1 <= n <= 2 * 104n - 1 <= edges.length <= 4 * 104edges[i].length == 31 <= ui, vi <= nui != vi1 <= weighti <= 105- 任意兩個節(jié)點之間至多存在一條邊
- 任意兩個節(jié)點之間至少存在一條路徑
分析：這個是要先算出各個點到n點的最短路徑，這個的話就應(yīng)該是迪杰斯特拉算法了，然后放在dist[]中記錄，然后就要搜索所有的路徑根據(jù)dist[]的要求去剪枝，這種搜索的話我想到的是回溯，如果這條路可以走的話進行剪枝，但是我看題解好像更多人用的是動態(tài)規(guī)劃?，直接用dp[]表示1到i的受限路徑數(shù)，這樣會簡單很多，這樣放一起來想的話，回溯更適合那種要求寫出路徑的，像這種只求路徑數(shù)的更適合動態(tài)規(guī)劃
#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.到達目的地的方案數(shù)
你在一個城市里，城市由?n?個路口組成，路口編號為?0?到?n - 1?，某些路口之間有?雙向?道路。輸入保證你可以從任意路口出發(fā)到達其他任意路口，且任意兩個路口之間最多有一條路。
給你一個整數(shù)?n?和二維整數(shù)數(shù)組?roads?，其中?roads[i] = [ui, vi, timei]?表示在路口?ui?和?vi?之間有一條需要花費?timei?時間才能通過的道路。你想知道花費?最少時間?從路口?0?出發(fā)到達路口?n - 1?的方案數(shù)。
請返回花費?最少時間?到達目的地的?路徑數(shù)目?。由于答案可能很大，將結(jié)果對?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 出發(fā)到路口 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- 任意兩個路口之間至多有一條路。
- 從任意路口出發(fā)，你能夠到達其他任意路口。
分析：我剛開始只想到了要用迪杰斯特拉算法計算出最小路徑，然后再用動態(tài)規(guī)劃計算路徑數(shù)目，但是到計算路徑數(shù)目的時候被難到了，總想著要用回溯去找路徑，后來看了別人的題解才的發(fā)現(xiàn)有一個性質(zhì)是：如果是合法路徑，那么在途中經(jīng)過的每一個點都是以最短路徑的方式到達的，也就是說，走到這里消費的時間其實就是dist[i]
那么就可以用dp[i]記錄走到這里等于dist[i]的數(shù)目，然后更新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}