之后的題解偏重有用/總結(jié)性質(zhì)，盡量理解算法本身而不是題，時(shí)間復(fù)雜度什么的也能夠放放。

非常久之前做過這個(gè)題，當(dāng)時(shí)使用dijkstra做的，關(guān)于幾個(gè)最短路算法，分類的話能夠分為下面幾種。

1、單源最短路：已知起點(diǎn)（終點(diǎn)），計(jì)算從源點(diǎn)到其它各個(gè)頂點(diǎn)的最短路徑長度。

典型算法：Dijkstra，Bellman-Ford（能夠算負(fù)的，比較慢），spfa（負(fù)權(quán)能用，加了松弛操作，速度比較炸天）

2、全局最短路：從一點(diǎn)到還有一點(diǎn)，典型如Floyd，A*啟示式算法。

又一次用floyd寫一遍：

#include <iomanip> #include <string.h> #include <iostream> using namespace std;const int INF=0x3f3f3f3f; int map[305][305]; int path[305][305]; bool visited[10005]; int prev[10005]; int waypoint;void clearmap() {for (int i=0;i<105;i++){for (int j=0;j<105;j++){map[i][j]=INF;}}memset(path,INF,sizeof(path));memset(prev,0,sizeof(prev));memset(visited,0,sizeof(visited)); }void floyd() {for(int k=0;k<waypoint;k++){for(int i=0;i<waypoint;i++){for(int j=0;j<waypoint;j++){if(map[i][k]!=INF && map[k][j]!=INF){if(map[i][j]>map[i][k]+map[k][j]){map[i][j]=map[i][k]+map[k][j];path[i][j]=path[k][j];}}}}} }int main() {int route;while (cin>>waypoint>>route){clearmap();for(int i=0;i<route;i++){int a,b,dis;cin>>a>>b>>dis;if(map[a][b]>dis){map[a][b]=map[b][a]=dis; }}floyd();int start,end;cin>>start>>end;if(start==end){cout<<0<<endl;}else if(map[start][end]!=INF)cout<<map[start][end]<<endl;elsecout<<"-1"<<endl;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/hrhguanli/p/3929625.html

總結(jié)

以上是生活随笔為你收集整理的【floyd】HDU 1874 畅通project续的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。