本文主要是介绍shuoj-小6爱夜跑--Floyd记录多个最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
自从小6学了最短路算法之后，就成了一个不折不扣的最短路理论拥护者，每次在校园里夜跑的时候，只要确定好起点和终点他就能快速算出最短的路径。然而小6却没有走过每一条路，只是对这些路径长度做了一个粗略估计，于是每条路就有了估计值与实际值的差距。小6想要知道从起点到终点，按照其中任意一条预估的最短路径跑，实际最长可能需要走过的路程。（因为同一长度的最短路可能有多个）
Input
多组输入，第一行是一个整数T，表示输入数据的组数(T≤20)。
接下来有T组数据，每组数据的第一行是四个整数N、M、S、E，分别代表图中的顶点数、边数、起点编号和终点编号。
(2≤N≤100, 1≤M≤1000, 1≤S,T≤N, S≠T)
之后的M行每行有四个整数u, v, a, b，代表图中编号为u的点到编号为v的点有一条双向边。
每条边有两个值a、b分别代表这条边的估计长度与实际长度。
(1≤u,v≤N, 1≤a,b≤1000, u ≠ v)
数据保证两个顶点间至多只有一条双向边相连，起点与终点间必定存在通路。
Output
对于每组输入，输出一行两个整数并换行，表示小6估算出的最短路长度以及实际最长可能需要走过的路程，两个整数间有一个空格。
Sample Input
Sample Output
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
vector<ll> path[120][120];ll c[120][120];
ll d[120][120];
ll max_load(int x,int y){if(path[x][y].empty())return d[x][y];for(int i = 0;i<path[x][y].size();i++){ll ans = path[x][y][i];return max(d[x][y],max_load(ans,y)+max_load(x,ans));}
}
int main(){int T;cin>>T;while(T--){for(int i = 0;i<120;i++)for(int j = 0;j<120;j++)path[i][j].clear();int m,n,s,e;cin>>n>>m>>s>>e;int u,v,a,b;for(int i = 0;i<n;i++)for(int j = 0;j<n;j++)c[i][j] = 2000;for(int i = 0;i<n;i++)c[i][i] = 0;for(int i = 0;i<m;i++){cin>>u>>v>>a>>b;u--;v--;c[u][v] = a;c[v][u] = a;d[u][v] = b;d[v][u] = b;}for (int k =0 ; k< n; k++){for (int i = 0; i< n; i++){for (int j = 0; j< n; j++)if (c[i][j] > c[i][k] + c[k][j]){c[i][j] = c[i][k]+c[k][j];path[i][j].clear();path[i][j].push_back(k);}else if (c[i][j] == c[i][k] + c[k][j] && k!= i &&k !=j)path[i][j].push_back(k);}}cout<<c[s-1][e-1]<<" ";cout<<max_load(s-1,e-1)<<endl;}return 0;
}
这篇关于shuoj-小6爱夜跑--Floyd记录多个最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
