POJ 1502 MPI Maelstrom

Description

n个点（1~n）

半个矩阵表示两点距离，x表示无穷大。（自己到自己的距离为0，矩阵里不包含这部分）

求1到所有点中最远点的最小距离

prepare

字符串转int

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int a = atoi(s.c_str());
    cout << a << '\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

https://blog.csdn.net/u013497977/article/details/50908342

Floyd

邻接矩阵存图，最短路更新在里面

Code of Floyd

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;///最短路、最小生成树

int n;
int mp[105][105];

void floyd()
{
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(mp[i][j] > mp[i][k] + mp[k][j])
                    mp[i][j] = mp[i][k] + mp[k][j];
    int ans = -1;
    for(int i = 1; i <= n; ++i)
        if(mp[1][i] > ans)
            ans = mp[1][i];
    cout << ans << '\n';
}

int main()
{
    scanf("%d", &n);
    memset(mp, INF, sizeof(mp));
    for(int i = 1; i <= n; ++i)
        mp[i][i] = 0;
    string s;
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j < i; ++j)///我常犯的错误:都int j了，还++i
        {
            cin >> s;
            if(s == "x")
                mp[i][j] = mp[j][i] = INF;
            else
                mp[i][j] = mp[j][i] = atoi(s.c_str());
        }
    floyd();
    return 0;
}
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

Bellman_Ford

结构体存边，以“点数次”(n)遍历所有边(cnt)去松弛

Code of Bellman_Ford

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, dis[105];

int cnt;
struct edge
{
    int from, to, w;
} a[10005];

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    cnt++;
    a[cnt].from = to;
    a[cnt].to = from;
    a[cnt].w = w;
    cnt++;
}

///现在看看这算法也挺暴力的：以“点数次”(n)遍历所有边(cnt)去松弛
bool Bellman_Ford(int start)///以遍历边为基础
{
    dis[start] = 0;
    int tot = n;
///n次松弛(这算法好牛，看看怎么实现的。Later，算了，能用就行)
    while(tot--)
    {
        bool flag = 0;///优化
        for(int i = 0; i < cnt; ++i)///遍历所有边
            if(dis[ a[i].to ] > dis[ a[i].from ] + a[i].w)
            {
                flag = 1;
                dis[ a[i].to ] = dis[ a[i].from ] + a[i].w;
            }
        if(!flag)
            break;
    }
    for(int i = 0; i < cnt; ++i)
        if(dis[ a[i].to ] > dis[ a[i].from ] + a[i].w)
            return 0;
    return 1;
}

int main()
{
    scanf("%d", &n);
    memset(dis, INF, sizeof(dis));
    cnt = 0;
    string s;
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j < i; ++j)
        {
            cin >> s;
            if(s == "x")
                add(i, j, INF);
            else
                add(i, j, atoi(s.c_str()));
        }
    if(Bellman_Ford(1))
    {
        int ans = -1;
        for(int i = 1; i <= n; ++i)
            if(dis[i] > ans && dis[i] != INF)
                ans = dis[i];
        cout << ans << '\n';
    }
    return 0;
}
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

Dijkstra

每次找到离源点最近的一个顶点，然后以该顶点为中心，然后得到源点到其他顶点的最短路径。贪心算法。

Code of Dijkstra

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

int n;

int cnt;
struct edge
{
    int from, to, w, pre;
} a[10005];

bool vis[105];
int head[105], dis[105];

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
    a[cnt].from = to;
    a[cnt].to = from;
    a[cnt].w = w;
    a[cnt].pre = head[to];
    head[to] = cnt;
    cnt++;
}

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
    {
        dis[i] = INF;
        head[i] = -1;
        vis[i] = 0;
    }
}

///分两部分①②
void dijkstra(int start)
{
    dis[start] = 0;
    int pos = start;
    int mmin;
    while(pos != -1)
    {
        ///①利用当前点更新未连入图的点到起点的最短距离
        ///注意：pos是中转点，不再是a[i].from!
        for(int i = head[pos]; ~i; i = a[i].pre)
        {
            if(vis[ a[i].to ])
                continue;
            if(dis[ a[i].to ] == INF || dis[ a[i].to ] > dis[pos] + a[i].w)
                dis[ a[i].to ] = dis[pos] + a[i].w;
        }
        vis[pos] = 1;

        ///②找到下一个距离起点最近的未连入线的点
        pos = -1;
        mmin = -1;
        for(int i = 1; i <= n; ++i)
            if(!vis[i] && dis[i] != INF && (dis[i] < mmin || mmin == -1))
            {
                mmin = dis[i];
                pos = i;
            }
    }
    return ;
}

int main()
{
    scanf("%d", &n);
    init();
    string s;
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j < i; ++j)
        {
            cin >> s;
            if(s == "x")
                add(i, j, INF);
            else
                add(i, j, atoi(s.c_str()));
        }
    dijkstra(1);
    int ans = -1;
    for(int i = 1; i <= n; ++i)
        if(dis[i] > ans && dis[i] != INF)
            ans = dis[i];
    cout << ans << '\n';
    return 0;
}
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
89
90
91
92
93
94
95
96
97
98
99
100

spfa

感觉像是广义的dijkstra，“最短路期望”…

Code of spfa

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

int n;

int cnt;
struct edge
{
    int from, to, w, pre;
} a[10005];

bool vis[105];///表示是否在队列里
int head[105], dis[105], times[105], tot, sum;

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
    a[cnt].from = to;
    a[cnt].to = from;
    a[cnt].w = w;
    a[cnt].pre = head[to];
    head[to] = cnt;
    cnt++;
}

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
    {
        dis[i] = INF;
        head[i] = -1;
        vis[i] = 0;
        times[i] = 0;
    }
}

bool spfa(int start)
{
    deque<int> q;
    dis[start] = 0;
    q.push_front(start);
    vis[start] = 1;///表示在队列里
    tot = 1, sum = 0;
    while(q.size())
    {
        int first = q.front();
        q.pop_front();
        vis[first] = 0;
        tot--;
        sum -= dis[first];

///同dijkstra，以first为中转点，而非a[i].from
        for(int i = head[first]; ~i; i = a[i].pre)
        {
            int t = a[i].to;
            if(dis[t] > dis[first] + a[i].w)
            {
                dis[t] = dis[first] + a[i].w;
                if(!vis[t])
                {
                    vis[t] = 1;
                    if(q.empty() || dis[t] > dis[q.front()] || dis[t] * tot >= sum)
                        q.push_back(t);
                    else
                        q.push_front(t);
                    sum += dis[t];
                    tot++;
                    if(++times[t] >= n)///这里是t
                        return 0;
                }
            }
        }
    }
    return 1;
}

int main()
{
    scanf("%d", &n);
    init();
    string s;
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j < i; ++j)
        {
            cin >> s;
            if(s == "x")
                add(i, j, INF);
            else
                add(i, j, atoi(s.c_str()));
        }
    if(spfa(1))
    {
        int ans = -1;
        for(int i = 1; i <= n; ++i)
            if(dis[i] > ans && dis[i] != INF)
                ans = dis[i];
        cout << ans << '\n';
    }
    return 0;
}
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113