频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu Minimum Transport Cost(按字典序输出路径)
2014-05-16 11:31:27         来源:hdu Minimum Transport Cost(按字典序输出路径)  
收藏   我要投稿

 

求最短路,要求输出字典序最小的路径。

 

spfa:拿一个pre[]记录前驱,不同的是在松弛的时候,要考虑和当前点的dis值相等的情况,解决的办法是dfs找出两条路径中字典序较小的,pre[]去更新。把路径当做字符串处理。

我只用之前的pre去更新当前点,并没考虑到起点到当前点的整个路径,其实这样并不能保证是字典序最小。wa了N次,于是乎搜了下题解,发现用spfa解的很少,看到了某大牛的解法如上,感觉很赞的想法。

 

 

#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;

int n;
int tax[maxn];
int Map[maxn][maxn];
int dis[maxn],inque[maxn];
int pre[maxn];
int pos = 0;

void dfs(int u, char *s)
{
	if(u == -1)
		return;
	dfs(pre[u],s);
	s[pos++] = u+'0';
}

bool solve(int v, int u)
{
	char s1[maxn],s2[maxn];
    
    //寻找先前的路径
	pos = 0;
	dfs(v,s1);
	s1[pos] = '';
    //寻找由u更新的路径
	pos = 0;
	dfs(u,s2);
	s2[pos++] = v+'0';
	s2[pos] = '';

	if(strcmp(s1,s2) > 0) return true;
	return false;

}

int spfa(int s, int t)
{
	queue  que;
	memset(dis,INF,sizeof(dis));
	memset(inque,0,sizeof(inque));
	memset(pre,-1,sizeof(pre));

	dis[s] = 0;
	inque[s] = 1;
	que.push(s);

	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inque[u] = 0;

		for(int v = 1; v <= n; v++)
		{
			if(Map[u][v] > 0)
			{
				int tmp = dis[u] + Map[u][v] + tax[v];

				if(tmp < dis[v])//直接更新
				{
					dis[v] = tmp;
					pre[v] = u;
					if(!inque[v])
					{
						inque[v] = 1;
						que.push(v);
					}
				}
				else if(tmp == dis[v] && solve(v,u))
				{
					pre[v] = u;
				}

			}
		}
	}

	return dis[t];
}

void output(int s, int t)
{
	int res[maxn];
	int cnt = 0;
	int tmp = t;

	while(pre[tmp] != -1)
	{
		res[cnt++] = tmp;
		tmp = pre[tmp];
	}
	res[cnt] = s;
	printf(Path: );
	for(int i = cnt; i >= 1; i--)
		printf(%d-->,res[i]);
	printf(%d
,res[0]);
}

int main()
{
	while(~scanf(%d,&n) && n)
	{
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
				scanf(%d,&Map[i][j]);
		}
		for(int i = 1; i <= n; i++)
			scanf(%d,&tax[i]);
		int u,v;
		while(~scanf(%d %d,&u,&v))
		{
			if(u == -1 && v == -1) break;
			int tmp1 = tax[u];//备份
			int tmp2 = tax[v];
			
			tax[u] = 0;
			tax[v] = 0;

			printf(From %d to %d :
,u,v);
			int ans = spfa(u,v);
			output(u,v);
			printf(Total cost : %d

,ans);
            //恢复备份
			tax[u] = tmp1;
			tax[v] = tmp2;


		}
	}
	return 0;
}

 

 


floyd:pre[i][j]记录i到j路径上距离i最近的点,输出路径时按pre正向输出。感觉floyd很强大啊,还可以这样记录路径。

 

 

#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn =  110;
int Map[maxn][maxn];
int tax[maxn];
int pre[maxn][maxn];
int n;


void floyd()
{
    //初始化
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            pre[i][j] = j;

    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(Map[i][k] > 0 && Map[k][j] > 0)
                {
                    int tmp = Map[i][k] + Map[k][j] + tax[k];

                    if(tmp < Map[i][j]) //小于直接更新
                    {
                        Map[i][j] = tmp;
                        pre[i][j] = pre[i][k];
                    }
                    else if(tmp == Map[i][j]) 
                    {
                        pre[i][j] = min(pre[i][k],pre[i][j]);
                    }
                }
            }
        }
    }
}

void output(int s, int t)
{
    printf(Path: );
    int tmp = s;
    while(tmp != t)
    {
        printf(%d-->,tmp);
        tmp = pre[tmp][t];
    }
    printf(%d
,t);

}

int main()
{
    while(~scanf(%d,&n) && n)
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                scanf(%d,&Map[i][j]);
                if(Map[i][j] == -1)
                    Map[i][j] = INF;
            }

        for(int i = 1; i <= n; i++)
            scanf(%d,&tax[i]);

        int u,v;
        floyd();
        while(~scanf(%d %d,&u,&v))
        {
            if(u == -1 && v == -1) break;
            printf(From %d to %d :
,u,v);
            output(u,v);
            printf(Total cost : %d

,Map[u][v]);
        }
    }
    return 0;
}


 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 字典 路径
上一篇:HDU 4803 Poor Warehouse Keeper(贪心)
下一篇:HDU 4811 Ball(贪心)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站