牛客巅峰赛s2第八场D

王者C 数学+最短路 B站视频https://www.bilibili.com/video/BV1W5411G7cX?p=4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef pair<int,int> PII;
#define so sizeof
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define lb lower_bound
#define ub upper_bound


const db esp=1e-5;
const int N=5e2+10,M=1e3+10,Max=1e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型 有n个城市
     * @param m int整型 有m条路径
     * @param s int整型 起始城市坐标
     * @param t int整型 终点城市坐标
     * @param edge int整型vector<vector<>> 边的格式如下:[[u1,v1,a1,b1],[u2,v2,a2,b2],...]
     * @return int整型
     */

    struct E{
        db lg;ll c;
        E(db lg=0,ll c=0):lg(lg),c(c){};
        E operator+(E b){
            return E(lg+b.lg,c*b.c%mod);
        }
    };
    E g[N][N];
    ll C[M][M];
    db lgps[M];
    int minDist(int n, int m, int s, int t, vector<vector<int> >& edge) {
        // write code here
        for(int i=0;i<=Max;i++){
            C[i][0]=1;
            for(int j=1;j<=i;j++)
                C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
        lgps[0]=0;
        for(int i=1;i<=Max;i++)
            lgps[i]=lgps[i-1]+log(i);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[i][j]=(i==j)?E(0,1):E(inf*1.0,0);
        for(auto i:edge){
            int a=i[0], b=i[1], c=i[2], d=i[3];
            db lg=lgps[c]-lgps[c-d]-lgps[d];
            if(g[a][b].lg>lg)
                g[a][b]=E(lg,C[c][d]), g[b][a]=E(lg,C[c][d]);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    if(g[i][j].lg>g[i][k].lg+g[k][j].lg)
                        g[i][j]=g[i][k]+g[k][j];
        }

        return g[s][t].c;
    }
}T;