0
已解决
姚炫好
资深守护
资深守护
题目链接: 酷町堂:6180
6180 密度最短路径
经验值:3200
时间限制:1000毫秒
内存限制:128MB
题目描述 De**ion
输入一个n个点m条边的有权有向无环图。现在定义路径密度为,路径长度除以路径上的边数。接下来有若干个询问,要分别求出某两点u到v的最小路径密度。
输入描述 Input De**ion
第一行,两个整数,n m
接下来m行,每行三个整数,u v w,从u到v的路径长度为w
再下来一行,一个整数q
再接下来q行,每行两个整数,u v,为要查询的一对边
输出描述 Output De**ion
对于每个询问输出一行,表示该询问的最小密度路径的密度(保留3位小数),如果不存在这么一条路径输出“OMG!”(不含引号)
样例输入 Sample Input
3 3 1 3 5 2 1 6 2 3 6 2 1 3 2 3
样例输出 Sample Output
5.000 5.500
数据范围及提示 Data Size & Hint
n<=40,m<=1000,1<=w,q<=100000
图中有重边
#include<bits/stdc++.h>
using namespace std;
const int maxn=45;
int n,m,q;
double f[maxn][maxn][maxn];
double d[maxn][maxn];
void floyd() {
for(int t=2; t<=n; t++)
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
f[i][j][t]=min(f[i][j][t],f[i][k][t-1]+f[k][j][1]);
}
int main(){
cin>>n>>m;
memset(f,0x3f,sizeof(f));
memset(d,0x3f,sizeof(d));
for(int i=1; i<=m; i++) {
int u,v,w;
cin>>u>>v>>w;
f[u][v][1]=min(f[u][v][1],w);
}
floyd();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
for(int k=1; k<=n; k++)
if(f[i][j][k]!=0x3f3f3f3f) d[i][j]=min(d[i][j],f[i][j][k]*1.0/k);
cin>>q;
for(int i=1; i<=q; i++) {
int x,y;
cin>>x>>y;
if(d[x][y]==0x3f3f3f3f) cout<<"OMG!"<<endl;
else printf("%.3f\n",d[x][y]);
}
return 0;
}
d[i][j]=min(d[i][j],f[i][j] [k]*1.0/k) ;
找出为什么报错就行了
请不要勒索我!!!!!
main.cpp: In function ‘int main()’: main.cpp:21:36: error: no matching function for call to ‘min(double&, int&)’ 21 | f[u][v][1]=min(f[u][v][1],w); | ^ In file included from /usr/include/c++/9/bits/char_traits.h:39, from /usr/include/c++/9/ios:40, from /usr/include/c++/9/istream:38, from /usr/include/c++/9/sstream:38, from /usr/include/c++/9/complex:45, from /usr/include/c++/9/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54, from main.cpp:1: /usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: ‘template constexpr const _Tp& std::min(const _Tp&, const _Tp&)’ 198 | min(const _Tp& __a, const _Tp& __b) | ^~~ /usr/include/c++/9/bits/stl_