频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdoj 1385 Minimum Transport Cost(dijkstar+字典路径||floyd+字典路径)
2012-07-12 17:21:06           
收藏   我要投稿


题目大意:开始时输入n表示一个n*n的矩阵, 该矩阵表示从i到j要多少钱, 然后输入经过每个城市时要的税, 起点和终点不需要缴税。要求输出最小花费路径, 并是字典顺序。
Ps:法克, 输出格式时比如1到1是 Path: 1, 而不是Path: 1-->1;就这个法克错一下午啊!

code:dijkstar+字典路径
#include <stdio.h> 
#include <string.h> 
#define inf 0x7fffffff 
int n = 0, start = 0, end = 0, map[1002][1002], tax[1002], path[1002], used[1002], dis[1002]; 
int cmp(int a, int b, int c) 

    int cur = 0, path1[1002] = {0}, path2[1002] = {0}, count1 = 0, count2 = 0; 
    path1[count1++] = c, path2[count2++] = c;//path1与path2存的是到c点的路径 
    for(cur = a; cur != -1; cur = path[cur]) 
        path1[count1++] = cur; 
    for(cur = b; cur != -1; cur = path[cur]) 
        path2[count2++] = cur; 
    count1--, count2--; 
    while(count1 != -1 || count2 != -1) 
    { 
        if(path1[count1]>path2[count2]) 
            return b; 
       else if(path1[count1]<path2[count2]) 
            return a; 
        count1--, count2--; 
    } 
    if(count1 == -1) 
        return a; 
    else 
        return b; 

void dijkstar() 

    int i = 0, j = 0, k = 0, min = 0; 
    for(i = 1; i<=n; i++) 
    { 
        path[i] = -1; 
        used[i] = 0; 
    } 
    for(i = 1; i<=n; i++) 
    { 
        dis[i] = map[start][i]; 
    } 
    used[start] = 1; 
    for(i = 0; i<n; i++) 
    { 
        min = inf; 
        for(j = 1; j<=n; j++) 
            if(!used[j] && min>dis[j] ) 
            { 
                min = dis[j]; 
                k = j; 
            } 
        used[k] = 1; 
        for(j = 1; j<=n; j++) 
        { 
            if(map[k][j] == inf) continue; 
            if(!used[j] && dis[j]>dis[k]+map[k][j]+tax[k]) 
            { 
                dis[j] = dis[k]+map[k][j]+tax[k]; 
                path[j] = k; 
            } 
            else if(!used[j] && dis[j]==dis[k]+map[k][j]+tax[k])//选取字典序小的 
            { 
                path[j] = cmp(path[j], k, j);//判断j的前面是path[j]还是k 
            } 
        } 
    } 

void print(int cur) 

    if(path[cur] != -1) 
        print(path[cur]); 
    printf("-->%d", cur); 

int main() 

    int i = 0, j = 0; 
    while(scanf("%d",&n) , n) 
    { 
        for(i = 1; i<=n; i++) 
            for(j = 1; j<=n; j++) 
            { 
                scanf("%d",&map[i][j]); 
                if(map[i][j] == -1) 
                    map[i][j] = inf; 
            } 
        for(i = 1; i<=n; i++) 
            scanf("%d",&tax[i]); 
        while(scanf("%d %d",&start, &end), start != -1 && end != -1) 
        { 
            dijkstar(); 
            printf("From %d to %d :\nPath: %d", start, end, start); 
            if(start != end) 
                print(end); 
            printf("\n"); 
            printf("Total cost : %d\n\n",dis[end]); 
        } 
    } 
    return 0; 

 


code: floyd+字典路径
path[i][j] 中存的是i到j路径的第2个点, 比如1->2->3, path[1][3]存的是2, path[2][3] = 3;
#include <stdio.h> 
#include <string.h> 
#define inf 0x7fffffff 
int n = 0, start = 0, end = 0, map[1002][1002], tax[1002], path[1002][1002]; 
void floyd() 

    int i = 0, j = 0, k = 0, item = 0; 
    for(i = 1; i<=n; i++) 
        for(j = 1; j<=n; j++) 
            path[i][j] = j; 
    for(k = 1; k<=n; k++) 
        for(i = 1; i<=n; i++) 
        { 
            if(i == k) continue; 
            for(j = 1; j<=n; j++) 
            { 
                if(map[i][k] == inf || map[k][j] == inf) continue; 
                item = map[i][k]+map[k][j]+tax[k]; 
                if(map[i][j]>item) 
                { 
                    map[i][j] = item; 
                    path[i][j] = path[i][k]; 
                } 
                else if(path[i][j]>path[i][k] && map[i][j]==item) 
                    path[i][j] = path[i][k]; 
            } 
        } 

void print() 

    int cur = start; 
    printf("From %d to %d :\nPath: %d", start, end, start); 
    while(cur != end) 
    { 
        printf("-->%d",path[cur][end]); 
        cur = path[cur][end]; 
    } 
    printf("\nTotal cost : %d\n\n", map[start][end]); 

int main()   www.2cto.com

    int i = 0, j = 0; 
    while(scanf("%d",&n) , n) 
    { 
        for(i = 1; i<=n; i++) 
        { 
            for(j = 1; j<=n; j++) 
            { 
                scanf("%d",&map[i][j]); 
                if(map[i][j] == -1) 
                    map[i][j] = inf; 
            } 
        } 
        for(i = 1; i<=n; i++) 
            scanf("%d",&tax[i]); 
        floyd(); 
        while(scanf("%d %d",&start, &end), start != -1 && end != -1) 
        { 
            print(); 
        } 
    } 
    return 0; 


作者:ulquiorra0cifer
点击复制链接 与好友分享!回本站首页
相关TAG标签 字典 路径
上一篇:poj 3468 A Simple Problem with Integers
下一篇:HDOJ 1757 A Simple Math Problem
相关文章
图文推荐
点击排行

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

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