HDU - 3790 - 最短路径问题

素颜马尾好姑娘i 2022-06-12 10:40 102阅读 0赞

--------------------

题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=3790][http_acm.hdu.edu.cn_showproblem.php_pid_3790]

## 题目描述 ##

### Description ###

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

### Input ###

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。  
(1

### Output ###

输出 一行有两个数， 最短距离及其花费。

### Sample Input ###

3 2  
1 2 5 6  
2 3 4 5  
1 3  
0 0

### Sample Output ###

9 11

## 解题思路 ##

1.  把G数组也就是各个点组成的map，全部记为inf 无限大，然后读取数值，更改两点之间的长度
2.  dis数组初始为直接连点的长度，即图上显示直接连接的长度，如果没有就记为inf
3.  vis数组初始先标记起点

更新dis数组：

1.  找到离起点，即与0最近的点
2.  vis标记这个点
3.  用这个点为中转站，判断到终点哪个更短
4.  更新到dis数组中
5.  这样dis存的点为起点到各个点的最短距离了

更详细的过程：[http://blog.csdn.net/xiao\_bai\_9527/article/details/75647518][http_blog.csdn.net_xiao_bai_9527_article_details_75647518]

## AC代码 ##

#include<iostream>
    #include<cstring> 
    #define inf 0x3f3f3f3f 
    using namespace std;
    int vis[10010];
    struct {
        int w, v;
    }s[1010][1010], dis[1010];
    void init(int n) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                s[i][j].w = s[i][j].v = inf;
            }
        }
        for(int i = 1; i <= n; i++)
            dis[i].v = dis[i].w = inf;
    }
    void dijkstra(int st, int ed, int n) {
        dis[st].w = 0;
        dis[st].v = 0;
        memset(vis, 0, sizeof(vis));
        for(int cnt = 1; cnt <= n; cnt++) {
            int minn = inf;
            int u = - 1;
            for(int i = 1; i <= n; i++) {
                if(vis[i] == 0 && dis[i].w < minn) {
                    minn = dis[i].w;
                    u = i;
                }
            }
            if(u == -1) break;
            vis[u] = 1;
            for(int i = 1; i <= n; i++) {
                if(dis[i].w > dis[u].w + s[u][i].w || (dis[i].w == dis[u].w + s[u][i].w && dis[i].v > dis[u].v + s[u][i].v)) {
                    dis[i].w = dis[u].w + s[u][i].w;
                    dis[i].v = dis[u].v + s[u][i].v;
                } 
            }
        }
    }
    int main () {
        int n, m;
        while(~scanf("%d %d", &n, &m) && n+m) {
            init(n);
            int x, y, w, v;
            for(int i = 1; i <= m; i++) {
                scanf("%d %d %d %d", &x, &y, &w, &v);
                if(s[x][y].w > w || (s[x][y].w == w && s[y][x].v > v)) {
                    s[x][y].w = s[y][x].w = w;
                    s[x][y].v = s[y][x].v = v;
                }
            }
            int st, ed;
            scanf("%d %d", &st, &ed);
            dijkstra(st, ed, n);
            printf("%d %d\n", dis[ed].w, dis[ed].v);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_3790]: http://acm.hdu.edu.cn/showproblem.php?pid=3790
[http_blog.csdn.net_xiao_bai_9527_article_details_75647518]: http://blog.csdn.net/xiao_bai_9527/article/details/75647518