题意

有个点和条边。从点到点，所需要的最小时间是多少，通过一条边的时间为组合数，答案对取模。

题解

若存粹的这是一道最短路的模板题，那么关于怎么处理边权这是一个点。首先若直接将边权赋为取模后的组合数的话，那么就会失去原本数大小的信息，所以不能这样进行比较。

，直接用大数存的话可能会超时，所以我们可以想着用别的方法来处理。如何能保留组合数大小的信息呢，我们可以对阶乘进行取对数，那么，除法也就变成了对数的减法。所以我们可以预处理出阶乘的对数，如何求出组合数的对数，这样就能吧组合数大小的信息保留下来了。接下来使用最短路算法就可以了，例如使用堆优化的dijkstra算法，我们开两个数组一个double类型的dist用来存log大小的组合数，在进行比较时，对于log的加分就变成了内部组合数的乘法，所以刚好是契合取log的组合数的。另一个long long类型的ans数组存实际上取模过的组合数，还需要初始化所有ans数组为1，并特判若起点终点为相同城市时输出0，这样就可以在做最短路的时候一起处理掉ans了。最后将ans[t]返回即使答案。对于组合数我们可以利用杨辉三角的方法来对组合数打表预处理出组合数。

复杂度

时间复杂度为
空间复杂度为

代码

const int N=1005;
const int mod=1e9+7;
long long C[N][N];
double L[N];
struct qnode
{
    int v;
    double c;
    qnode(int _v=0,double _c=0):v(_v),c(_c) {}
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v,a,b;
    long long c;
    double cost;
    Edge(int _v=0,int _a=0,int _b=0):v(_v),a(_a),b(_b){
        c=C[a][b];
        cost=L[a]-L[b]-L[a-b];
    }
};
vector<Edge>E[N];
bool vis[N];
long long ans[N];
double dist[N];
priority_queue<qnode>que;
void Dijstra(int n,int beg)
{
    for(int i=1; i<=n; i++)
    {
        vis[i]=0;
        dist[i]=1e9;
        ans[i]=1;
    }
    dist[beg]=0;
    while(!que.empty())
        que.pop();
    que.push(qnode(beg,0));
    while(!que.empty())
    {
        qnode tem=que.top();
        que.pop();
        int u=tem.v;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0; i<E[u].size(); i++)
        {
            int v=E[u][i].v;
            double cost=E[u][i].cost;
            if(dist[v]>dist[u]+E[u][i].cost)
            {
                dist[v]=dist[u]+E[u][i].cost;
                ans[v]=(ans[u]*E[u][i].c)%mod;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}
void addedge(int u,int v,int a,int b)
{
    E[u].push_back(Edge(v,a,b));
}
void get_C()
{
    C[0][0] = 1;
    for(int i=1;i<N;i++)
    {
        C[i][0] = 1;
        for(int j=1;j<=i;j++)
            C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
    }
}
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整型
     */
    int minDist(int n, int m, int s, int t, vector<vector<int> >& edge) {
        // write code here
        if(s==t)
            return 0;
        get_C();
        for(int i=1;i<N;i++)
            L[i]=L[i-1]+log(i);
        for(int i=0;i<m;i++)
        {
            addedge(edge[i][0],edge[i][1],edge[i][2],edge[i][3]);
            addedge(edge[i][1],edge[i][0],edge[i][2],edge[i][3]);
        }
        Dijstra(n,s);
        return ans[t];
    }
};