1.胡会因此矩阵快速幂呢。Alice和Bob现在一经起一个城沿航线达任何一个都。

原题: FZU 2173 http://acm.fzu.edu.cn/problem.php?pid=2173

Description

Alice和Bob现在设趁飞机旅行,他们捎了平等寒相对有利的航空企业。该航空企业合在n个城市有业务,设这些都会分别标记为0至n-1,一共有m种航线,每种航线连接两个都市,并且航线有得的价格。Alice和Bob现在要从一个都市沿航线达任何一个城池,途中可以进行之际。航空企业针对她们这次旅行啊出优惠,他们得免费于无比多k种航线上添就飞机。那么Alice和Bob这次出行最少花费多少?

一如既往开始看此题毫无头绪,根本无悟出是矩阵快速幂,其实看见k那么大,就相应想到用便捷幂什么的,况且n<=50,可以用矩阵来代表图。

Input

多少的首先执行有三单整数,n,m,k,分别代表都屡屡,航线数与免费乘坐次数。

亚行有三三两两独整数,s,t,分别代表他们出行的起点城市编号与极端都编号。(0<=s,t<n)

接通下去有m行,每行三个整数,a,b,c,表示是同样栽航线,能打城市a到达都会b,或打市b到达都市a,价格也c。(0<=a,b<n,a与b不对等,0<=c<=1000)

 

1.胡能够就此矩阵快速幂呢?

Output

 

就发一行,包含一个整数,为至少花费。

原理:

Sample Input

5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

原始矩阵m[][]中,m[u][v]代表u到v的花,求矩阵的k次幂后,此时m[u][v]意味着,从u走向b经过v步的无限少花费
留意这矩阵的相乘应该写成:
m[a][b]=min(m[a][1]+m[1][b],…m[a][n]+m[n][b])
 ,即取最小价如果非相加。

Sample Output

8

2.怎么吧?

HINT

对于30%的数据,2<=n<=50,1<=m<=300,k=0;

对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;

对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.

确立分支图。
f[u][t]意味着以节点u时已经免费乘坐t次的极其少花
消费。照样跑不过缺少路程。
枚举与u相连的装有节点v,w(u,v)表示权值。
若t<k:
f[v][t+1]=min(f[v][t+1],f[u][t])
对此有:
f[v][t]=min(f[v][t],f[u][t]+w(u,v))

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 struct Node
 8 {
 9   int next,to,dis;
10 }edge[100001];
11 struct XXX
12 {
13   int x;
14   int k;
15 };
16 int num,head[100001],dist[100001][11],n,m,k,S,T,ans;
17 bool vis[100001][11];
18 void add(int u,int v,int d)
19 {
20   num++;
21   edge[num].next=head[u];
22   head[u]=num;
23   edge[num].to=v;
24   edge[num].dis=d;
25 }
26 void SPFA()
27 {int i;
28   queue<XXX> Q;
29   Q.push((XXX){S,0});
30   dist[S][0]=0;
31   while (Q.empty()==0)
32   {
33     XXX u=Q.front();
34     Q.pop();
35     vis[u.x][u.k]=0;
36     for (i=head[u.x];i;i=edge[i].next)
37       {int v=edge[i].to;
38     if (dist[v][u.k]>dist[u.x][u.k]+edge[i].dis)
39       {
40         dist[v][u.k]=dist[u.x][u.k]+edge[i].dis;
41         if (vis[v][u.k]==0)
42           {
43         vis[v][u.k]=1;
44         Q.push((XXX){v,u.k});
45           }
46       }
47     if (u.k+1<=k&&dist[v][u.k+1]>dist[u.x][u.k])
48       {
49         dist[v][u.k+1]=dist[u.x][u.k];
50         if (vis[v][u.k+1]==0)
51           {
52         vis[v][u.k+1]=1;
53         Q.push((XXX){v,u.k+1});
54           }
55       }
56       }
57   }
58 }
59 int main()
60 {int i,u,v,c;
61   cin>>n>>m>>k;
62   memset(dist,127/3,sizeof(dist));
63   scanf("%d%d",&S,&T);
64   for (i=1;i<=m;i++)
65     {
66       scanf("%d%d%d",&u,&v,&c);
67       add(u,v,c);
68       add(v,u,c);
69     }
70   SPFA();
71   ans=2e9;
72   for (i=0;i<=k;i++)
73     ans=min(ans,dist[T][i]);
74   cout<<ans;
75 }

 

m的1次方,无疑是不易的。

m的2次方
此时(m[a][b])^2=min(m[a][1]+m[1][b],..m[a][n]+m[n][b]),就是枚举a经过1届n点再到b的极少花费,就是a经过简单步到达b的绝少花费

归纳法:

如果(m[a][b])^i代表了a走i步到达b的极端少花费,则m^(i+1)=min((m[a][1])^i+m[1][b],…(m[a][n])^i+m[n][b])

因此可以如此做。

(借鉴nothing的博客)

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define Mod 1000000007
#define lll __int64
using namespace std;
#define N 6007

struct Matrix
{
    lll m[55][55];
};
int n,h,k;

Matrix Mul(Matrix a,Matrix b)
{
    Matrix c;
    memset(c.m,-1,sizeof(c.m));
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            for(int k=0;k<n;k++)
            {
                if(a.m[i][k]!=-1&&b.m[k][j]!=-1)
                {
                    if(c.m[i][j] == -1)
                        c.m[i][j] = a.m[i][k]+b.m[k][j];
                    else
                        c.m[i][j] = min(c.m[i][j],a.m[i][k]+b.m[k][j]);
                }
            }
        }
    return c;
}

Matrix fastm(Matrix a,int n)
{
    if(n == 1)
        return a;
    Matrix res = fastm(a,n/2);
    res = Mul(res,res);
    if(n&1)
        res = Mul(res,a);
    return res;
}

Matrix MPow(Matrix a,int n)  //第二种写法
{
    Matrix res = a;
    n--;
    while(n)
    {
        if(n&1)
            res = Mul(res,a);
        n>>=1;
        a = Mul(a,a);
    }
    return res;
}

int main()
{
    int t,i,j,k;
    int u,v;
    lll w;
    Matrix A,ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&h,&k);
        memset(A.m,-1,sizeof(A.m));
        for(i=0;i<h;i++)
        {
            scanf("%d%d%I64d",&u,&v,&w);
            u--,v--;
            if(A.m[u][v] == -1)
                A.m[u][v] = w;
            else
                A.m[u][v] = min(A.m[u][v],w);
        }
        ans = MPow(A,k);
        printf("%I64d\n",ans.m[0][n-1]);
    }
    return 0;
}

View Code