前置知识

• SPFA（此题解的优化是基于 SPFA 的，跑起来效率惊人，甚至比官方标程还快）

• 树状数组

题目

有 m 条双向边，每条有两个权值 c_i, t_i，求两点之间的最短路长度。

本题最短路定义：没有其他同时满足 Σc_i​ 和 Σt_i​ 都不比它小（当然，如果有两个值都相等的两条路径，只计一次贡献）的路径。

思路

由于此题与一般最短路不同，边有两种权值，所以需要在每个节点处增加一维状态。即用 dp[i][j] 表示在 i 点且已用费用为 j 时的最短时间，则有：dp[i][j] = min{dp[k][i - cost[k][i]] + time[k][i] | For each edge(k, i)}.

由此，我们可以直接用 SPFA 算法求解。期望时间复杂度为 O(KN²V)。已经比官方标程跑的快了

优化

虽然实际算法运行的很快，然而状态会达到 100³ 的级别，优化空间还很大。

在迭代求解过程中，考虑任意一新状态 dp[i][j]，如果已经存在一状态 dp[i][k]，满足 k<j 且 dp[i][k]<dp[i][j]，则显然 dp[i][j] 不是最优解，我们也就没有更新（将其加入队列）的必要。

于是可以加入这样一个剪枝：对于每个新状态 dp[i][j]，我们查询 dp[i][0...j] 的最小值 minTime，当 dp[i][j]<minTime 时再进行更新。在实现时我们可以使用树状数组维护 dp[i] ，以加快查询速度。

期望时间复杂度 O(KN²V log N)，而实际效率惊人，是官方标程的十倍多。

代码

#define lowbit(x) ((x)&(-x))
const int MAXN=1e4+5;
int nxt[605],v[605],w[605],to[605],head[605],q[1000005][2],dis[105][MAXN],tree[105][MAXN],cnt,n,m,s,t,ans;
bool vis[105][MAXN];
void treearr_add(int x,int y,int val)
{
    y++;        //树状数组不支持下标为0，故+1
    while(y<=n*100)
    {
        tree[x][y]=min(tree[x][y],val);
        y+=lowbit(y);
    }
    return;
}
int treearr_sum(int x,int y)
{
    int res=1e7;
    y++;
    while(y)
    {
        res=min(res,tree[x][y]);
        y-=lowbit(y);
    }
    return res;
}
void g_addedge(int a,int b,int c,int d)     //加边！加边！加边！注意有两个边权
{
    nxt[++cnt]=head[a];
    head[a]=cnt;
    to[cnt]=b;
    v[cnt]=c;
    w[cnt]=d;
    return;
}
void g_sp_SPFA()
{
    int x,f1,y,f2;
    memset(dis,0x3f,sizeof(dis));
    memset(tree,0x3f,sizeof(tree));
    dis[s][0]=0;
    q[1][0]=s;
    q[1][1]=0;
    treearr_add(s,0,0);
    for(int h=1,t=1;h<=t;h++)
    {
        x=q[h][0];
        f1=q[h][1];
        vis[x][f1]=false;
        for(int i=head[x];i;i=nxt[i])
        {
            y=to[i];
            f2=f1+w[i];
            if(treearr_sum(y,f2)>dis[x][f1]+v[i])       //若满足条件，则可能对答案有贡献
            {
                dis[y][f2]=dis[x][f1]+v[i];
                treearr_add(y,f2,dis[y][f2]);
                if(!vis[y][f2])
                {
                    vis[y][f2]=true;
                    q[++t][0]=y;
                    q[t][1]=f2;
                }
            }
        }
    }
    return;
}
int main()
{
    int a,b,c,d,mind;
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d %d",&a,&b,&c,&d);
        g_addedge(a,b,d,c);
        g_addedge(b,a,d,c);
    }
    g_sp_SPFA();
    mind=dis[0][0];
    for(int i=0;i<=n*100;i++)       //费用递增，时间递减
    {
        if(dis[t][i]<mind)
        {
            mind=dis[t][i];
            ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}