题解 CF576D 【Flights for Regular Customers】

对每条边来说，可以走这条边的限制解除是按\(d\)的顺序，所以先对每条边按\(d\)排序。

然后考虑每两条边之间的处理，用一个矩阵表示当前走\(d\)步是否可以从一个点到另一个点，称其为状态矩阵，用另一个矩阵表示当前解除了限制的边，称其为边矩阵。

每次新加入一条边时，让状态矩阵乘上当前边矩阵的\(d_i-d_{i-1}\)次方，即可更新走当前步数\(d\)步点与点之间到达的状态，这一过程可以用矩阵快速幂和\(bitset\)进行优化。

然后用\(floyd\)处理出以当前解除限制的边的最短路，若起点能通过\(d\)步到达一个点，那么就用这个点到终点的最短路径加上\(d\)来更新答案。

具体实现看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 200

#define all 150

#define inf 200000000000

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

ll n,m,ans=inf;

ll f[maxn][maxn];

struct edge

{

    int x,y,d;

}ed[maxn];

bool cmp(const edge &x,const edge &y)

{

    return x.d<y.d;

}

struct matrix

{

	bitset<maxn> a[maxn];

	matrix()

	{

        for(int i=1;i<=all;++i) a[i].reset();

	}

}t;

matrix operator *(const matrix &x,const matrix &y)

{

    matrix z;

    for(int k=1;k<=n;++k)

    	for(int i=1;i<=n;++i)

        	if(x.a[i][k])

        		z.a[i]|=y.a[k];

	return z;

}

int main()

{

    read(n),read(m);

    for(int i=1;i<=m;++i)

        read(ed[i].x),read(ed[i].y),read(ed[i].d);

    sort(ed+1,ed+m+1,cmp);

    for(int i=1;i<=n;++i) t.a[i][i]=1;

    for(int p=1;p<=m;++p)

    {

        matrix e;

        for(int i=1;i<p;++i) e.a[ed[i].x][ed[i].y]=1;

        ll k=ed[p].d-ed[p-1].d;

        while(k)

        {

            if(k&1) t=t*e;

            e=e*e,k>>=1;

        }

        for(int i=1;i<=n;++i)

        {

            for(int j=1;j<=n;++j)

            {

                if(i==j) f[i][j]=0;

                else f[i][j]=inf;

            }

        }

        for(int i=1;i<=p;++i) f[ed[i].x][ed[i].y]=1;

        for(int k=1;k<=n;++k)

            for(int i=1;i<=n;++i)

                for(int j=1;j<=n;++j)

                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

        for(int i=1;i<=n;++i)

            if(t.a[1][i])

                ans=min(ans,ed[p].d+f[i][n]);

    }

    if(ans==inf) puts("Impossible");

    else printf("%lld",ans);

    return 0;

}

巴特西

题解 CF576D 【Flights for Regular Customers】

最新文章

热门文章