Aizu - 2200 Mr. Rito Post Office

题意：/*你是某个岛国（ACM-ICPC Japan）上的一个苦逼程序员，
你有一个当邮递员的好基友利腾桑遇到麻烦了：
全岛有一些镇子通过水路和旱路相连，走水路必须要用船，在X处下船了船就停在X处。
而且岛上只有一条船，下次想走水路还是得回到X处才行；
两个镇子之间可能有两条以上的水路或旱路；
邮递员必须按照清单上的镇子顺序送快递
（镇子可能重复，并且对于重复的镇子不允许一次性处理，比如ABCB的话B一定要按顺序走两次才行）。*/

思路:弗洛伊德求出弗洛伊德求出陆路，水路任意两点间的最短距离，然后动态规划求解。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<vector>

#include<set>

#include<queue>

#include<string>

#include<algorithm>

#define MAXSIZE 1005

#define LL long long

#define INF 0x3f3f3f

using namespace std;

int lmap[MAXSIZE][MAXSIZE],smap[MAXSIZE][MAXSIZE],dp[MAXSIZE][MAXSIZE],q[MAXSIZE],n,m;

int solve()

{

    for(int k=;k<=n;k++) //弗洛伊德求出陆路，水路任意两点间的最短距离

    {

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

        {

            for(int j=;j<=n;j++)

            {

                lmap[i][j] = min(lmap[i][j],lmap[i][k]+lmap[k][j]);

                smap[i][j] = min(smap[i][j],smap[i][k]+smap[k][j]);

            }

        }

    }

    dp[][q[]] = ; //初始在第一个城市

    for(int i=;i<=m;i++) //现在派送的城市

    {

        for(int j=;j<=n;j++) //枚举船在那个城市

        {

            dp[i][j] = min(dp[i][j],dp[i-][j]+lmap[q[i-]][q[i]]);

            for(int k=;k<=n;k++) //枚举把船停到那个城市

            {

                dp[i][k] = min(dp[i][k],dp[i-][j]+lmap[q[i-]][j]+smap[j][k]+lmap[k][q[i]]);

            }

        }

    }

    int minn = INF;

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

    {

        if(minn > dp[m][i])

            minn = dp[m][i];

    }

    return minn;

}

void Init()

{

    for(int i=;i<MAXSIZE;i++)

    {

        for(int j=;j<MAXSIZE;j++)

        {

            if(i == j)

            {

                //dp[i][j] = 0;

                lmap[i][j] = ;

                smap[i][j] = ;

            }

            else

            {

                lmap[i][j] = INF;

                smap[i][j] = INF;

            }

            dp[i][j] = INF;

        }

    }

}

int main()

{

    char op[];

    int u,v,w;

    while(scanf("%d%d",&n,&m),n+m)

    {

        Init();

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

        {

            scanf("%d%d%d%s",&u,&v,&w,op);

            if(op[] == 'L')

            {

                lmap[u][v] = lmap[v][u] = min(lmap[u][v],w);

            }

            else

            {

                smap[u][v] = smap[v][u] = min(smap[u][v],w);

            }

        }

        scanf("%d",&m);

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

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

        int ans = solve();

        printf("%d\n",ans);

    }

    return ;

}

巴特西

Aizu - 2200 Mr. Rito Post Office

最新文章

热门文章