频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU 1385 Minimum Transport Cost(最短路,打印字典序路径)
2012-10-16 09:41:14           
收藏   我要投稿

题目大意:
有N个城市,然后直接给出这些城市之间的邻接矩阵,矩阵中-1代表那两个城市无道路相连,其他值代表路径长度。
如果一辆汽车经过某个城市,必须要交一定的钱(可能是过路费)。
现在要从a城到b城,花费为路径长度之和,再加上除起点与终点外所有城市的过路费之和。
求最小花费,如果有多条路经符合,则输出字典序最小的路径。


分析与总结:
1.   这题的关键在于按照字典序输出路径。
假设有
1--->2  2
2--->3  1
1--->3  3
求1到3的最小花费路径.
那么显然后两条路:
1-->3   3
1-->2-->3  3
它们的花费是相同的,但是路径的字典序不同,“123”比“13”字典序要小,所以应当输出1-->2-->3.

2.   用一个数组pre记录每一点的上一个结点。按照一般的单源最短路算法,在松弛时是有“小于”就直接松弛, 而这题还要判断“等于”的情况,在“等于”之时,这是要选择哪一个父结点所形成的路径字典序较小,就选择哪一个父结点。
所以,在“等于”之时,可以求出原先的路径, 再求出当前这个的路径,把路径转化成字符串,然后直接比较大小决定是否要换父结点。

3.  求路径的方法并转化为字符串的方法, 其实很简单,用一个3行的递归函数就解决了。


4. 本题学到的新东西:
之后在网上搜题解,发现还可以用Floyd算法来解决,很神奇,再次感叹Floyd算法的强大,自己也只理解了个皮毛。


代码:
1. SPFA
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<queue> 
using namespace std; 
 
const int INF = 0x7fffffff; 
const int VN  = 105; 
 
int n; 
int w[VN][VN]; 
int charge[VN]; 
int d[VN]; 
int pre[VN]; 
bool inq[VN]; 
int pos=0; 
 
void init(){ 
    for(int i=0; i<=n; ++i){ 
        w[i][i] = INF; 
        for(int j=i+1; j<=n; ++j) 
            w[i][j]=w[j][i]=INF; 
    } 

 
// 获得从开始点到当前点的路径,转化成字符串 
void dfs(int u, char *str){ 
    if(u==-1)return; 
    dfs(pre[u],str); 
    str[pos++] = u+'0'; 

 
bool cmp(int origin, int now){ 
    char str1[100], str2[100]; 
 
    //1. 获取原来的路径 
    pos=0; 
    dfs(origin,str1); 
    str1[pos] = '\0'; 
     
    //2.获取当前点的路径 
    pos=0; 
    dfs(now, str2); 
    str2[pos++] = origin+'0';  
    str2[pos]   = '\0'; 
 
    //3.比较是否比原来的字典序小 
    if(strcmp(str1, str2)==1)return true; 
    return false; 

 
void SPFA(int src){ 
    memset(inq, 0, sizeof(inq)); 
    memset(pre, -1, sizeof(pre)); 
    int i,j; 
    for(i=1; i<=n; ++i) d[i]=INF; 
    d[src] = 0; 
    queue<int>q; 
    q.push(src); 
    while(!q.empty()){ 
        int u = q.front(); q.pop(); 
        inq[u] = false; 
        for(int v=1; v<=n; ++v)if(w[u][v]!=INF){ 
            int tmp = d[u]+w[u][v]+charge[v]; 
            if(d[v] > tmp){ 
                d[v] = tmp; 
                pre[v] = u; 
                if(!inq[v]){ 
                    inq[v] = true; 
                    q.push(v); 
                } 
            } 
            else if(d[v] == tmp && cmp(v, u)){ 
                pre[v] = u;  
            } 
        }  
    } 

// 打印路径 
void print_path(int u){ 
    if(pre[u]==-1){ 
        printf("%d",u); 
        return; 
    } 
    print_path(pre[u]); 
    printf("-->%d",u);   

int main(){ 
      
    int i,j,src,des; 
    while(scanf("%d",&n),n){ 
        init(); 
        for(i=1; i<=n; ++i){ 
            for(j=1; j<=n; ++j){ 
                scanf("%d",&w[i][j]); 
                if(w[i][j]==-1) w[i][j]=INF; 
            } 
        } 
        for(i=1; i<=n; ++i) 
            scanf("%d",&charge[i]); 
 
        while(scanf("%d%d",&src,&des)){ 
            if(src==-1&&des==-1) break; 
            // 备份 
            int tmp1=charge[src], tmp2=charge[des]; 
            charge[src]=0, charge[des]=0; // 起始点和终点Tax收费为0 
            SPFA(src);       
            printf("From %d to %d :\n",src,des); 
            printf("Path: "); 
            print_path(des); 
            printf("\nTotal cost : %d\n\n", d[des]); 
            // 恢复 
            charge[src]=tmp1, charge[des]=tmp2; 
        } 
         
    } 
    return 0; 


2. Floyd 记录路径
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<queue> 
using namespace std; 
 
const int INF = 0x7fffffff; 
const int VN  = 105; 
 
int n; 
int w[VN][VN]; 
int path[VN][VN]; 
int charge[VN]; 
 
void init(){ 
    for(int i=0; i<=n; ++i){ 
        for(int j=0; j<=n; ++j){ 
            if(i!=j)w[i][j]=INF; 
            else w[i][j]=0; 
            path[i][j] = j;  // path[i][j]表示点i到j经过的第一个点` 
        } 
    } 

 
void Floyd(){ 
    for(int k=1; k<=n; ++k) 
    for(int i=1; i<=n; ++i) 
    for(int j=1; j<=n; ++j)if(w[i][k]!=INF && w[k][j]!=INF){ 
        int tmp = w[i][k]+w[k][j]+charge[k]; 
        if(w[i][j] > tmp){ 
            w[i][j] = tmp; 
            path[i][j] = path[i][k]; 
        } 
        else if(w[i][j] == tmp && path[i][j]>path[i][k]){ 
            path[i][j] = path[i][k]; 
        } 
    } 
}    
 
int main(){ 
      
    int i,j,src,des; 
    while(scanf("%d",&n),n){ 
        init(); 
        for(i=1; i<=n; ++i){ 
            for(j=1; j<=n; ++j){ 
                scanf("%d",&w[i][j]); 
                if(w[i][j]==-1) w[i][j]=INF; 
            } 
        } 
        for(i=1; i<=n; ++i) 
            scanf("%d",&charge[i]); 
 
        Floyd(); 
        while(scanf("%d%d",&src,&des)){ 
            if(src==-1&&des==-1) break; 
            printf("From %d to %d :\n",src,des); 
            printf("Path: "); 
            int u = src; 
            printf("%d",u); 
            while(u != des){ 
                printf("-->%d",path[u][des]); 
                u = path[u][des]; 
            } 
            puts(""); 
            printf("Total cost : %d\n\n", w[src][des]); 
        } 
         
    } 
    return 0; 


 

点击复制链接 与好友分享!回本站首页
相关TAG标签 字典 路径
上一篇:[C/C++学习]之十五、内存管理
下一篇: HDU 1224 Free DIY Tour
相关文章
图文推荐
点击排行

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

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