问题描述:

给你一张由$T$条边构成的无向图,求起点$S$到终点$E$恰好经过$N$条边的最道路。(路径可以重复经过)

输入:

第一行包含4个整数$N$、$T$、$S$、$E$ ($N<=1000000,T<=100$,节点编号不超过1000)
接下来T行每行三个数$Len,I_1,I_2$ 表示$I_1 I_2$间有一条长度为$Len$的无向边

输出:

一个整数,起点$S$到终点$E$恰好经过$N$条边的最道路长度

思路:

将这个与矩阵加速递推联系起来确实需要对递推有很深的理解(需要很大脑洞)。。。

其实我们每进行一次递推就是多经过一条路径,然后每一次进行递推时都需要将所有点之间的距离初始化一下(如果不初始化就是普通的最短路,初始化了就是经过N条边的最短路)。

我们的递推可以利用类似Floyd的方式来实现。如果直接开$1000*1000$的矩阵复杂度显然会爆掉,于是我们考虑只有100条边,那么最多只有200个点是有用的,因此我们先离散化一下。最后按照套路利用矩阵快速幂优化一下递推就能够过了。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int n, m, t, s, e, tot, sub[205], f[205][205], g[205][205];

struct A {int s, t, len;} a[205];

void mul(int x[205][205], int y[205][205])
{
    int ans[205][205];
    memset(ans, 0x3f, sizeof(ans));
    for(int k=1; k<=m; k++)
        for(int i=1; i<=m; i++)
            for(int j=1; j<=m; j++)
                ans[i][j]=min(ans[i][j], x[i][k]+y[k][j]);
    memcpy(x, ans, sizeof(ans));
}

int main()
{
    memset(f, 0x3f, sizeof(f));
    scanf("%d%d%d%d", &n, &t, &s, &e);
    sub[++tot]=s; sub[++tot]=e;
    for(int i=1; i<=t; i++)
    {
        scanf("%d%d%d", &a[i].len, &a[i].s, &a[i].t);
        sub[++tot]=a[i].s; sub[++tot]=a[i].t;
    }
    sort(sub+1, sub+tot+1);
    m=unique(sub+1, sub+tot+1)-sub-1;
    for(int i=1; i<=t; i++)
    {
        int x=lower_bound(sub+1, sub+m+1, a[i].s)-sub;
        int y=lower_bound(sub+1, sub+m+1, a[i].t)-sub;
        f[x][y]=min(f[x][y], a[i].len);
        f[y][x]=min(f[y][x], a[i].len);
    }
    memcpy(g, f, sizeof(g));
    n--;
    while(n)
    {
        if(n&1) mul(g, f);
        mul(f, f); n>>=1;
    }
    s=lower_bound(sub+1, sub+m+1, s)-sub;
    e=lower_bound(sub+1, sub+m+1, e)-sub;
    printf("%d\n", g[s][e]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注