HDOJ 2544 最短路

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2544

Dijkstra最简单的应用—直接套模版。注意这一题要考虑重路,也就是输入的两点A,B相同,这时存储的要是其中最小的C。

Dijkstra分析与实现(C/C++)见:
http://www.wutianqi.com/?p=1890

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Author:   Tanky Woo
// Blog:       www.WuTianqi.com
#include <iostream>
using namespace std;
 
const int maxnum = 105;
const int maxint = 1001;
 
 
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
    bool s[maxnum];    // 判断是否已存入该点到S集合中
    for(int i=1; i<=n; ++i)
    {
        dist[i] = c[v][i];
        s[i] = 0;     // 初始都未用过该点
        if(dist[i] == maxint)
            prev[i] = 0;
        else
            prev[i] = v;
    }
    dist[v] = 0;
    s[v] = 1;
 
    // 依次将未放入S集合的结点中,取dist[]最小值的结点,放入结合S中
    // 一旦S包含了所有V中顶点,dist就记录了从源点到所有其他顶点之间的最短路径长度
    for(int i=2; i<=n; ++i)
    {
        int tmp = maxint;
        int u = v;
        // 找出当前未使用的点j的dist[j]最小值
        for(int j=1; j<=n; ++j)
            if((!s[j]) && dist[j]<tmp)
            {
                u = j;              // u保存当前邻接点中距离最小的点的号码
                tmp = dist[j];
            }
        s[u] = 1;    // 表示u点已存入S集合中
 
        // 更新dist
        for(int j=1; j<=n; ++j)
            if((!s[j]) && c[u][j]<maxint)
            {
                int newdist = dist[u] + c[u][j];
                if(newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
    }
}
 
int main()
{
    freopen("input1.txt", "r", stdin);
    // 各数组都从下标1开始
    int dist[maxnum];     // 表示当前点到源点的最短路径长度
    int prev[maxnum];     // 记录当前点的前一个结点
    int c[maxnum][maxnum];   // 记录图的两点间路径长度
    int n, line;             // 图的结点数和路径数
 
    while(scanf("%d %d", &n, &line) && (n || line))
    {
        int p, q, len;          // 输入p, q两点及其路径长度
 
        // 初始化c[][]为maxint
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                c[i][j] = maxint;
 
        for(int i=1; i<=line; ++i)
        {
            cin >> p >> q >> len;
            c[p][q] = len;      // p指向q
            c[q][p] = len;      // q指向p,这样表示无向图
        }
        for(int i=1; i<=n; ++i)
            dist[i] = maxint;
 
 
        Dijkstra(n, 1, dist, prev, c);
 
        // 最短路径长度
        cout << dist[n] << endl;
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 2544 最短路》有14个想法

  1. 咦?我刚刚的回复怎么没显示。。。博主,你程序中maxint=1001太小,而题目中的M可以达到10000,所以就有点问题啦。

  2. 不好意思,再一次麻烦博主了,我的代码为什么AC不了,我已经做了很多组的测试了:
    http://blog.csdn.net/panyanyany/article/details/6302493这个里面的数据都能通过,出了最后一组违法数据。怎么就是AC不了,郁闷.自己看完全看不出来哪里有问题。。
    #include
    #include
    #include
    #include
    using namespace std;
    #define MAX_COST 1001
    #define N 101
    int array[N][N];

    int Dijistra(int n)
    {
    bool* flag = new bool[n + 1];
    int i, j, k;
    for(i = 1; i <= n; ++i)
    flag[i] = false;

    flag[1] = true;
    //n个顶点需要循环n次
    for(i = 1; i <= n; ++i)
    {
    int current;
    int temp = MAX_COST;
    //寻找新节点
    for(j = 1; j <= n; ++j)
    {
    if(flag[j] == true)
    {
    for(k = 1; k <= n; ++k)
    {
    if(flag[k] == false)
    {
    if(array[j][k] < temp)
    {
    current = k;
    temp = array[j][k];
    }
    }
    }
    }
    }

    flag[current] = true;
    for(j = 1; j <= n; ++j)
    {
    if(flag[j] == true && j != current)
    {
    for(k = 1; k (array[j][current] + array[current][k]))
    {
    array[j][k] = array[j][current] + array[current][k];
    }
    }
    }
    }
    }
    }
    delete []flag;
    return array[1][n];
    }
    int main()
    {
    int n, m, i, start, end, cost, g, h;
    //fstream input(“test.txt”);
    while(scanf(“%d%d”, &n, &m) != EOF && (n + m))
    //while(input >> n >> m && (n + m))
    {
    for(g = 1; g <= n; ++g)
    {
    for(h = 1; h <= n; ++h)
    {
    array[g][h] = MAX_COST;
    }

    }
    for(i = 0; i > start >> end >> cost;
    if(array[start][end] > cost)
    {
    array[end][start] = cost;
    array[start][end] = cost;
    }
    }
    printf(“%d\n”,Dijistra(n));
    }
    return 0;
    }

    1. 嗯,这题目可能有些数据没考虑到吧?要不就是HDOJ那边数据的问题了。我这道题目现在还没想好错误的测试用例,你那边呢?

    2. 我也纳闷死了,LS那朋友昨天让我帮忙看这题,我检查了好久一只WA,今天测试我的代码,居然也WA了,刚去看了下,发现HDOJ数据库丢失,结果我这题曾经的AC也没了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注