1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 0x14141414 using namespace std; typedef long long ll; int d[1005][105][105],V,E,Q; int (){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; } void init(){ V=read(),E=read(); int u,v,c; memset(d,0x14,sizeof(d)); for(int i=1;i<=E;i++){ u=read(),v=read(),c=read(); if(d[1][u][v]>c)d[1][u][v]=c; } for(int l=2;l<=E;l++) for(int k=1;k<=V;k++) for(int i=1;i<=V;i++) for(int j=1;j<=V;j++) d[l][i][j]=min(d[l][i][j],d[l-1][i][k]+d[1][k][j]); Q=read(); } void solve(){ int u,v; double ans; for(int i=1;i<=Q;i++){ u=read(),v=read(); ans=INF; for(int l=1;l<=E;l++) if(d[l][u][v]<INF) ans=min(ans,d[l][u][v]/(double)l); if(ans>INF-1)printf("OMG!n"); else printf("%.3lfn",ans); } } int main(){ init(); solve(); return 0; }
|
近期评论