B. Wycieczki

题目描述

给定一张n个点m条边的带权有向图，每条边的边权只可能是1，2，3中的一种。
将所有可能的路径按路径长度排序，请输出第k小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。

输入格式

第一行包含三个整数n,m,k(1<=n<=40，1<=m<=1000，1<=k<=10^18)。
接下来m行，每行三个整数u,v,c(1<=u,v<=n，u不等于v，1<=c<=3)，表示从u出发有一条到v的单向边，边长为c。
可能有重边。

输出格式

包含一行一个正整数，即第k短的路径的长度，如果不存在，输出-1。

样例

样例输入

样例输出

数据范围与提示

长度为1的路径有1->2，5->3，4->5。
长度为2的路径有2->3，3->4，4->5->3。
长度为3的路径有4->6，1->2->3，3->4->5，5->3->4。
长度为4的路径有5->3->4->5。

这道题时间跨度比较长了，主要是因为这道题贼难调，稍有不慎就会WA，而且这道题的测试点贼多，多到会出现2分情况，所以真的是我的签名说的，一杯茶一包纸，一份代码调成X

其实这道题还算好像，而且有思维量，主要就是要把边的矩阵拆点，然后建边，注意需点，也就是整个矩阵会扩大三倍;整个题其实就是二分（我打了一半，跑的实在是太慢了，所以换了一种方法）倍增，倍增就和求lca其实是一样的，就是换成了矩阵，不知其他神犇是怎么打的，反正我是使用结构体，但是要注意细节，整个卡了一晚上，就是因为矩阵传参没加取地址，加上就A了，有神犇知道为啥的就留言吧

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

using namespace std;

#define LL long long

#define re register

#define F(i,a,b) for(LL i=a;i<=b;i++)

LL n,m,u,v,d,t;

long long s,k;

bool flag;

inline LL read()

{

    re LL ss=;char bb=getchar();

    while(bb<||bb>)bb=getchar();

    while(bb>=&&bb<=)ss=(ss<<)+(ss<<)+(bb^),bb=getchar();

    return ss;

}

struct Martix

{

    LL x[][];

    void init()

    {

        memset(x,,sizeof(x));

    }

}mul[],tmp;

Martix bg,base,now;

void made(Martix &a,Martix &b,Martix &c)

{

    flag=;

    tmp.init();

    F(i,,*n+)

        F(l,,*n+)

        {

            if(!a.x[i][l])continue;

            //debug(i);debug(l);

            F(j,,*n+)

                tmp.x[i][j]=tmp.x[i][j]+a.x[i][l]*b.x[l][j];

            if(i==&&tmp.x[i][*n+]>=k)flag=;

        }

    c=tmp;

}

int main()

{

    //freopen("cnm.txt","r",stdin);

    n=read(),m=read(),k=read();

    F(i,,n)

    {

        bg.x[][i]=;

        base.x[i][i+n]=;

        base.x[i+n][i+*n]=;

    }

    while(m--)

    {

        u=read(),v=read(),d=read();

        base.x[u+(d-)*n][v]++;

        base.x[u+(d-)*n][*n+]++;

    }

    base.x[*n+][*n+]=;

    mul[]=base;

    for(;t<=;t++)

    {

        if(t)

            made(mul[t-],mul[t-],mul[t]);

        made(bg,mul[t],now);

        if(!flag||now.x[][*n+]>=k){break;}

    }

    t--;

    if(t==&&now.x[][*n+]<k)

    {

        puts("-1");

        return ;

    }

    for(LL i=t;i>=;i--)

    {

        made(bg,mul[i],now);

        if(flag&&now.x[][*n+]<k)

        {

            s+=(1ll<<i);

            bg=now;

        }

    }

    printf("%lld\n",s+);

}

hhh

endl;

巴特西

Wycieczki 线性代数