QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #563956 | #9293. Fine Trip | zjy0001 | WA | 0ms | 35368kb | C++14 | 855b | 2024-09-14 17:59:06 | 2024-09-14 17:59:06 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e3+5;
const LL INF=4e18;
int n,m;LL T,ans=INF,d[N][N];
vector<pair<int,LL>>G[N];
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>T;
if(n==1)return cout<<"0\n",0;
for(int i=1;i<=m;++i){
int u,v,l,c;cin>>u>>v>>l>>c;
G[u].emplace_back(v,1ll*l*c);
G[v].emplace_back(u,1ll*l*c);
}
memset(d,0x3f,sizeof(d));
d[0][1]=0;
for(int k=0;k<n;++k){
for(int u=1;u<=n;++u)if(d[k][u]<INF)
for(auto [v,w]:G[u])
d[k+1][v]=min(d[k+1][v],d[k][u]+w);
}
for(int k=1;k<=n;++k)
if(d[k][n]<=INF/k)ans=min(ans,d[k][n]*k);
cout<<fixed<<setprecision(10)<<1.L*ans/T<<'\n';
return 0;
}
/*
3 3 100
1 3 100 100
1 2 100 24
2 3 100 24
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 35332kb
input:
3 3 100 1 3 100 100 1 2 100 24 2 3 100 24
output:
96.0000000000
result:
ok found '96.0000000', expected '96.0000000', error '0.0000000'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 35368kb
input:
3 2 10 1 2 9 1 2 3 1 1000
output:
201.8000000000
result:
wrong answer 1st numbers differ - expected: '119.8736660', found: '201.8000000', error = '0.6834390'