HDU/HDOJ 1874 畅通工程续(SPFA)

这是以前用Dijkstra做的。

http://www.wutianqi.com/?p=1894

现在用SPFA再做一次~~~

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
// HDOJ 1874 SPFA
#include <iostream>
using namespace std;
 
const int MAXN = 1005;
const int INF = 99999;
//用数组实现邻接表存储,pnt[i,0]表示与i相邻的结点个数,pnt[i,1...k]存储与i相邻的点
//int  pnt[MAXN][MAXN];
int  map[MAXN][MAXN]; //map[i,j]为初始输入的i到j的距离,并且map[i,i]=0;未知的map[i,j]=INF;
int  dis[MAXN];
char vst[MAXN];
int Q[MAXN];
 
int SPFA(int n, int s)
{
    int i, pri, end, p, t;
    memset(vst, 0, sizeof(vst));
    for(int i=0; i<MAXN; ++i)
        Q[i] = 0;
    for (i=0; i<n; i++)
        dis[i] = INF;
    dis[s] = 0;
    vst[s] = 1;
    Q[0] = s; pri = 0; end = 1;
    while (pri < end)
    {
        p = Q[pri];
        for (i=0; i<n; ++i)
        {
            //先释放,释放成功后再判断是否要加入队列
            if (dis[p]+map[p][i] < dis[i])
            {
                dis[i] = dis[p]+map[p][i];
                if (!vst[i])
                {
                    Q[end++] = i;
                    vst[i] = 1;
                }
            }
        }
        vst[p] = 0;
        pri++;
    }
    return 1;
}
 
int M, N;
int start, end;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    while(cin >> N >> M)
    {
        for(int i=0; i<MAXN; ++i)
            for(int j=0; j<MAXN; ++j)
                map[i][j] = INF;
        int p, q, len;
        for(int i=1; i<=M; ++i)
        {
            cin >> p >> q >> len;
            if(len < map[p][q])
                map[p][q] = map[q][p] = len;
        }
        cin >> start >> end;
 
        SPFA(N, start);
        if(dis[end] < INF)
            cout << dis[end] << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

发布者

Tanky Woo

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

发表评论

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