做网站必须要切图吗,推广运营是什么工作,高密做网站哪家强价位,做本地网站要服务器吗之后的题解偏重有用/总结性质#xff0c;尽量理解算法本身而不是题#xff0c;时间复杂度什么的也能够放放。 非常久之前做过这个题#xff0c;当时使用dijkstra做的#xff0c;关于几个最短路算法#xff0c;分类的话能够分为下面几种。 1、单源最短路#xff1a;已知起… 之后的题解偏重有用/总结性质尽量理解算法本身而不是题时间复杂度什么的也能够放放。 非常久之前做过这个题当时使用dijkstra做的关于几个最短路算法分类的话能够分为下面几种。 1、单源最短路已知起点终点计算从源点到其它各个顶点的最短路径长度。 典型算法DijkstraBellman-Ford能够算负的比較慢spfa负权能用加了松弛操作速度比較炸天 2、全局最短路从一点到还有一点典型如FloydA*启示式算法。 又一次用floyd写一遍 #include iomanip
#include string.h
#include iostream
using namespace std;const int INF0x3f3f3f3f;
int map[305][305];
int path[305][305];
bool visited[10005];
int prev[10005];
int waypoint;void clearmap()
{for (int i0;i105;i){for (int j0;j105;j){map[i][j]INF;}}memset(path,INF,sizeof(path));memset(prev,0,sizeof(prev));memset(visited,0,sizeof(visited));
}void floyd()
{for(int k0;kwaypoint;k){for(int i0;iwaypoint;i){for(int j0;jwaypoint;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 (cinwaypointroute){clearmap();for(int i0;iroute;i){int a,b,dis;cinabdis;if(map[a][b]dis){map[a][b]map[b][a]dis; }}floyd();int start,end;cinstartend;if(startend){cout0endl;}else if(map[start][end]!INF)coutmap[start][end]endl;elsecout-1endl;}return 0;
}转载于:https://www.cnblogs.com/hrhguanli/p/3929625.html
