2/13每日总结

P1359 租用游艇

#include using namespace std;int a[210][210];int main (){memset(a,0x3f,sizeof(a)); //将数组a中所有值变成最大值int n;cin >> n;for(int i = 1;i <= n - 1;i ++){for(int j = i + 1;j <= n;j ++){if(i == j){a[i][j] = 0;}else{cin >> a[i][j]; //存i到j之间的价钱}}}for(int k = 1;k <= n;k ++) //Floyd算法for(int i = 1;i <= n;i ++)for(int j = 1;j <= n;j ++){a[i][j] = min(a[i][j],a[i][k] + a[k][j]);}cout << a[1][n];return 0;}

这是一个经典的Floyd算法的题

单源最短路径 ---- Dijkstra(迪杰斯特拉算法) 多源最短路径 ---- Floyd（弗洛伊德算法） Dijkstra算法 1 初始化： 先找出从源点 v0 到各终点vk 的直达路径（v0，vk），即通过一条弧到达的路径。 2 选择：从这些路径找出一条长度最短的路径（v0，u）。 3 更新：对其余各条路径进行适当调整 弗洛伊德算法 1逐个顶点试探 2从vi到vj中所有可能存在的路径中 3选出一条长度最短的路径