http://47.95.147.191/problem/P3

2021-04-15 01:26

阅读：617

标签：快速 ons == pac std ++ floyd amp 最短路

http://47.95.147.191/problem/P3
规定边数的最短路，跑floyd+矩阵快速幂

#include
#include
#include
#include
#include
#include
#includeset>
#include
#include
#include#define inf 2147483647
#define For(i,a,b) for(long long i=a;i#define p(a) putchar(a)
#define g() getchar()
#define mod 1000000007
//by war
//2020.2.26
using namespace std;
long long n,k,S,T,x,y,lim,c;
long long m[1010];
struct matrix{
    long long a[310][310];
    matrix operator*(const matrix&b)const{
        matrix r;
        For(i,1,n)
            For(j,1,n){
                r.a[i][j]=inf;    
                For(k,1,n)
                r.a[i][j]=min(r.a[i][j],a[i][k]+b.a[k][j]);
            }
        return r;
    }
}a;
void in(long long &x)
{
    long long y=1;
    char c=g();x=0;
    while(c‘0‘||c>‘9‘)
    {
    if(c==‘-‘)
    y=-1;
    c=g();
    }
    while(c‘9‘&&c>=‘0‘)x=(x1)+(x3)+c-‘0‘,c=g();
    x*=y;
}
void o(long long x)
{
    if(x0)
    {
        p(‘-‘);
        x=-x;
    }
    if(x>9)o(x/10);
    p(x%10+‘0‘);
}

matrix ksm(matrix a,long long b){
    matrix r=a;b--;
    while(b>0){
        if(b%2==1) r=r*a;
        a=a*a;
        b>>=1;
    }
    return r;
}

int main(){
    in(lim);in(k);in(S);in(T);
    For(i,0,300)
        For(j,0,300)
            a.a[i][j]=inf;
    For(i,1,k){
        in(c);in(x);in(y);
        if(!m[x]) m[x]=++n;
        if(!m[y]) m[y]=++n;
        a.a[m[x]][m[y]]=a.a[m[y]][m[x]]=c;
    }
    matrix r=ksm(a,lim);
    o(r.a[m[S]][m[T]]);
    return 0;
}

http://47.95.147.191/problem/P3

标签：快速 ons == pac std ++ floyd amp 最短路

原文地址：https://www.cnblogs.com/war1111/p/12368053.html

上一篇：Vue Loader 作用域CSS（scoped）——/deep/ 深入组件选择器

下一篇：Thinkphp 前端视图输出日期时间戳自动转换为时间格式化年月日

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：http://47.95.147.191/problem/P3
文章链接：http://soscw.com/index.php/essay/75873.html

亲，登录后才可以留言！

http://47.95.147.191/problem/P3

评论

热门文章

推荐文章

最新文章

置顶文章