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