[POI2015]WYC

传送 本人trl,不会a*启发式搜索。。

看到权值1,2,3显然拆点。

然后既然要问你第k短路径,可以考虑枚举长度为1路径有多少,长度为2有多少,找到第一个长度使得路径个数达到k

凡一步一步跳的都考虑倍增

然后就显然想到了倍增。

倍增处理后再一个一个减下来,复杂度降到log

最终复杂度大概O(跑得过)$O(n^3logk)$

当然,有个坑是你不能把拆点拆出的新点用来做路径终点QAQ 因为这个点根本不存在

然后如果倍增到了65还没发现大于k($2^{65}$已经炸了)肯定无解。

细节很多 处理一下因为一个中间变量没开longlongwa了几十遍

/*Heroes Never Die!*/
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 125
#define P 1000000000
typedef long long ll;
ll n , t , k;

struct matrx { ll a[MAXN][MAXN]; } G[70] , tmp , cur , inf ;

bool work( matrx& a ){
    ll p = 0;
    for( ll i = 1 ; i <= n ; ++ i )
        if( (k <= (p += a.a[i][0] - 1)) ) return true;
    return false;
}

void mul( matrx& x , matrx& y ) {
    for( ll i = 0 ; i <= 3*n ; ++ i )
        for( ll j = 0 ; j <= 3*n ; ++ j ) {
            tmp.a[i][j] = 0;
            for( ll p = 0 ; p <= 3*n ; ++ p ) 
                tmp.a[i][j] += x.a[i][p] * y.a[p][j];
        }
}


int main() {
    //freopen("input","r",stdin);
    ll m;
    cin >> n >> m >> k;
    G[0].a[0][0] = 1;
    for( ll i = 1 ; i <= n ; ++ i ) cur.a[i][i] = G[0].a[i][0] = G[0].a[i][i+n] = G[0].a[i+n][i+2*n] = 1;
    for( ll i = 0,u,v,w ; i < m ; ++ i ) {
        scanf("%lld%lld%lld",&u,&v,&w);
        ++ G[0].a[u+(w-1)*n][v];
    }
    ll i;
    for( i = 1 ;  ; ++ i ) {
        if( i > 65 ) return puts("-1"),0;
        mul( G[i-1] , G[i-1] ) , G[i] = tmp;
        if(work( G[i] )) break;
    }
    long long ans = 0;
    for( i-- ; ~i ; --i ) {
        mul( cur , G[i] );
        if( !work(tmp) ) cur = tmp , ans += (1ll<<i);
    }
    cout << ans ;
}
//qwq