FZU 2173 Nostop【Floyd+快速幂】

Accept: 128    Submit: 494Time Limit: 3000 mSec    Memory Limit : 32768 KB

 Problem Description

M国有N个城市，H条单向的道路，AekdyCoin从编号为1的城市出发，每经过一条道路要花一个单位的时间。假设他出发的时刻为0，他需要在K时刻到达编号为N的城市。并且，AekdyCoin不会在一个城市停留，每到一个城市他要立刻往下一个城市出发，最后在K时刻时他必须在城市N。虽然AekdyCoin经过任意一条道路的花费的时间都是1，但是每条道路的过路费不一定相同。现给出每条道路的过路费，问AekdyCoin从编号为1的城市出发，在K时刻到达编号为N的城市最小需要花费多少钱？注意AekdyCoin可以经过同一个城市任意多次，包括城市N。

 Input

第一行输入一个整数T表示数据组数，接下来输入T组数据。对于每组数据，第一行输入三个整数N，H,K(1<=N<=50,1<=H<=3000,1<=K<=1000000000)，接下来输入H行，每行三个整数u、v、cost（1<=u,v<=n,1<=cost<=1000000），表示从u到v过路费为cost的一条单行道。

 Output

对于每组数据输出一行一个整数表示最小花费，若无法在K时刻到达城市N，则输出-1。

 Sample Input

 Sample Output

思路：

题目和POJ 3613是一毛一样的；

1、首先我们要理解这样一个问题，如果a【i】【j】表示图的初始邻接矩阵，b【i】【j】==a【i】【j】；

如果c【j】【k】=min（c【j】【k】，a【j】【i】+b【i】【k】）{应用Floyd求最短路}，其实不难理解，c【】【】得到的邻接矩阵是从b中拿出一条边，从a中拿出一条边构成的，那么如果初始a和

b就是邻接矩阵，那么c【i】【j】现在表示的含义就是从i到j一共经过两条边的最短路。

2、那么推广，如果现在让a【i】【j】=c【i】【j】，那么现在a【i】【j】现在表示的含义就是从i到j一共经过两条边的最短路。此时b【i】【j】不变，还是图的邻接矩阵，如果这时候c【j】【k】=min（c【j】【k】，a【j】【i】+b【i】【k】）{应用Floyd求最短路}.那么c【】【】得到的邻接矩阵也是从a中拿出一条边，从b中拿出一条边构成的，然而这时候a中的一条边，其实相当于两条边，那么：c【i】【j】现在表示的含义就是从i到j一共经过三条边的最短路。

3、依次类推，如果需要经过k条边的从i到j的最短路，那么就进行k-1次上述过程即可。因为k可能比较大，而且每一次进行Floyd也是一个不小的开销，所以这k-1次乘法我们用快速幂的方式优化，最终得到正解。

4、注意初始化inf要足够大。

Ac代码：

#include<stdio.h>#include<string.h>#include<iostream>using namespace std;#define ll __int64const ll inf=1e18;ll b[70][70];ll c[70][70];ll a[70][70];ll n,h,k;void mul(ll a[70][70],ll b[70][70]){   for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c[i][j]=inf;    for(ll i=1;i<=n;i++)    {        for(ll j=1;j<=n;j++)        {            for(ll k=1;k<=n;k++)            {                if(a[j][i]==inf||b[i][k]==inf)continue;                c[j][k]=min(c[j][k],a[j][i]+b[i][k]);            }        }    }}void copy2(){    for(ll i=1;i<=n;i++)    {        for(ll j=1;j<=n;j++)        {            b[i][j]=c[i][j];        }    }}void Slove(ll k){    for(ll i=1;i<=n;i++)    {        for(ll j=1;j<=n;j++)        {            b[i][j]=a[i][j];        }    }    k--;    while(k>0)    {        if(k%2==1)        {            mul(b,a);            copy2();        }        k/=2;        mul(a,a);        for(ll i=1;i<=n;i++)        {            for(ll j=1;j<=n;j++)            {                a[i][j]=c[i][j];            }        }    }}int main(){    ll t;    scanf("%I64d",&t);    while(t--)    {        scanf("%I64d%I64d%I64d",&n,&h,&k);        //////////////////////        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                a[i][j]=inf;            }        }        for(ll i=0;i<h;i++)        {            ll x,y,w;            scanf("%I64d%I64d%I64d",&x,&y,&w);            a[x][y]=min(a[x][y],w);        }        Slove(k);        if(b[1][n]!=inf)        printf("%I64d/n",b[1][n]);        else printf("-1/n");    }}