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");    }}