小W旅游railway

---

对于一家铁路公司，我们可以首先使用 Floyd 算法求出任

意两点 x, y 间只经过属于该家铁路公司铁路的最短路，那么在新

图中我们在 x, y 间加一条 x 到 y 最短路对应的花费为边权的边。

接下来只要在新图中使用 Floyd 算法求出任意两点间的最

小花费就可以了。

跟昨天写的<跑路>有点像

http://blog.csdn.net/kenxhe/article/details/53072146

总结一下, floyd的优势在于可以求出任意两个点之间的距离, 可利用这种特性来构建新图, 解决问题.

代码不是我的, 将就着看吧

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1010;

int p[N],q[N][N],r[N][N],f[N][N][21],ans,cost[20010][21];

int n,m,tot,x,y,z,k,kk,s,t,dis[N][N],c[N][N],fa[N];

int fin(int x)

{

    if (fa[x]!=x)

        fa[x]=fin(fa[x]);

    return fa[x];

}

int main()

{

    memset(f,0x16,sizeof(f));

    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);

    for (int i=1;i<=n;i++) fa[i]=i;

    for (int i=1;i<=m;i++)

    {

        scanf("%d%d%d%d",&x,&y,&z,&kk);

        f[x][y][kk]=z;

        c[x][y]=kk;

        f[y][x][kk]=z;

        c[y][x]=kk;

        int fx=fin(x),fy=fin(y);

        if (fx!=fy)

            fa[fx]=fy;

    }

    int fs=fin(s),ft=fin(t);

    if (fs!=ft)

    {

        printf("-1\n");

        return 0;

    }

    for (int i=1;i<=k;i++)

        scanf("%d",p+i);

    for (int i=1;i<=k;i++)

    {

        for (int j=1;j<p[i];j++)

            scanf("%d",&q[i][j]);

        for (int j=1;j<=p[i];j++)

            scanf("%d",&r[i][j]);

    }

    for (int i=1;i<=k;i++)

        for (int j=1;j<=20000;j++)

        {

            int ii,ans=0;

            for (ii=1;ii<p[i];ii++)

            {

                if (j<q[i][ii]) break;

                ans+=(q[i][ii]-q[i][ii-1])*r[i][ii];

            }

            if (j>q[i][ii-1])

                ans+=(j-q[i][ii-1])*r[i][ii];

            cost[j][i]=ans;

        }

    for (int cc=1;cc<=k;++cc)

    for (int kk=1;kk<=n;kk++)

        for (int i=1;i<=n;i++) if (i!=kk)

            for (int j=1;j<=n;j++) if (i!=j)

                f[i][j][cc]=min(f[i][j][cc],f[i][kk][cc]+f[kk][j][cc]);

//              if (c[i][kk]==c[kk][j])

//                  f[i][j][c[kk][j]]=min(f[i][j][c[kk][j]],f[i][kk][c[i][kk]]+f[kk][j][c[kk][j]]);

    for (int i=1;i<=n;i++)

        for (int j=1;j<=n;j++) if (i!=j)

            for (int col=1;col<=k;col++)

            if (f[i][j][col]<20000000)

                f[i][j][col]=cost[f[i][j][col]][col];

    memset(dis,0x16,sizeof(dis));

    for (int i=1;i<=n;i++)

        for (int j=1;j<=n;j++) if (i!=j)

            for (int col=1;col<=k;col++)

                dis[i][j]=min(dis[i][j],f[i][j][col]);

    for (int kk=1;kk<=n;kk++)

        for (int i=1;i<=n;i++) if (i!=kk)

            for (int j=1;j<=n;j++) if (i!=j)

                dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]);

    printf("%d\n",dis[s][t]);

}