USACO 2007 Nov Gold 2.Cow Relays

2014.12.24 08:47 Wed| 9 visits oi_2015| 2015_刷题日常| Text

Problem

题目大意

求无向图中恰好经过N条边的最短路长度。

Solution

要是问题改成,无向图中恰好经过N条边的路径条数,就可以用矩阵乘法解决问题了!这里问最短路长度,那么将矩阵乘法改成Floyd即可!

0.0这是什么心态……

快速幂加速Floyd。真是醉了。。另外由于读入只有100条边而之多出现1000个点,很显然要离散化Hash。这里偷懒用map的最慢的写法也能过2333

Code

#include <bits/stdc++.h>
using namespace std;

#define N 205

struct matrix
{
    int n,dist[N][N];
    matrix(int _n=0,int clear=0x3f):n(_n)
    {
        memset(dist,clear,sizeof dist);
    }
    void print()
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cout<<dist[i][j]<<" \n"[j==n];
    }
};

matrix floyd(const matrix &a,const matrix &b)
{
    matrix re(a.n);
    for(int k=1;k<=re.n;k++)
        for(int i=1;i<=re.n;i++)
            for(int j=1;j<=re.n;j++)
                if(re.dist[i][j]>a.dist[i][k]+b.dist[k][j])
                    re.dist[i][j]=a.dist[i][k]+b.dist[k][j];
    return re;
}

matrix power(matrix mat,int k)
{
    matrix re(mat.n);
    for(int i=1;i<=re.n;i++)
        re.dist[i][i]=0;
    while(k)
    {
        if(k&1) re=floyd(re,mat);
        mat=floyd(mat,mat); k>>=1;
    }
    return re;
}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

matrix mat;
map<int,int> m;
int n,t,s,e,tot;

int main()
{
    cin>>n>>t>>s>>e;
    for(int x,y,z,i=1;i<=t;i++)
    {
        z=read(), x=read(), y=read();
        if(m.find(x)==m.end()) m[x]=++tot;
        if(m.find(y)==m.end()) m[y]=++tot;
        mat.dist[m[x]][m[y]]=mat.dist[m[y]][m[x]]=z;
    }
    mat.n=tot;
    cout<<power(mat,n).dist[m[s]][m[e]]<<endl;
}