Floyd小结

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
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn =  1005;
const int inf = 0x3f3f3f3f;

int grid[maxn][maxn];
int T,S,D;
int n;
vector<int> cityBegin,cityEnd;

void floyd() {
    for (int k=1; k<=n; ++k)
        for (int i=1; i<=n; ++i)
            if (grid[i][k] != inf)
                for (int j=1; j<=n; ++j)
                    grid[i][j] = min(grid[i][j],grid[i][k]+grid[k][j]);
}
void init() {
    n = 0;
    memset(grid,inf,sizeof grid);
    for (int i=1; i<1005; ++i)
        grid[i][i] = 0;
    while (!cityBegin.empty()) cityBegin.pop_back();
    while (!cityEnd.empty()) cityEnd.pop_back();
}
int main() {
    //freopen("1.in","r",stdin);
    while (scanf("%d%d%d",&T,&S,&D) != EOF) {
        init();
        int a,b,time;
        for (int i=1; i<=T; ++i) {
            scanf("%d%d%d",&a,&b,&time);
            grid[a][b] = min(grid[a][b],time);
            grid[b][a] = min(grid[b][a],time);
            a = max(a,b);    n = max(a,n);
        }
        for (int i=1; i<=S; ++i) {
            int from;
            scanf("%d",&from);
            cityBegin.push_back(from);
        }
        for (int i=1; i<=D; ++i) {
            int to;
            scanf("%d",&to);
            cityEnd.push_back(to);
        }
        floyd();
        int ans = inf;
        for (auto from:cityBegin)
            for (auto to:cityEnd)
                ans = min(ans,grid[from][to]);
        printf("%dn",ans);
    }
    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
#include <map>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int maxn = 35;

map<string,int> Hash;
int n,cnt;
double grid[maxn][maxn];
void floyd() {
    for (int k=0; k<cnt; ++k)
        for (int i=0; i<cnt; ++i)
            for (int j=0; j<cnt; ++j)
                grid[i][j] = max(grid[i][j],grid[i][k]*grid[k][j]);
}

int main() {
    freopen("1.in","r",stdin);
    int times = 1;
    while (scanf("%d",&n) && n) {
        cnt = 0;
        Hash.clear();
        memset(grid,0,sizeof grid);
        string temp;
        for (int i=1; i<=n; ++i) {
            cin >> temp;
            Hash.insert({temp,cnt++});
        }
        int m; scanf("%d",&m);
        for (int i=1; i<=m; i++) {
            string to;
            double rate;
            cin >> temp >> rate >> to;
            grid[Hash[temp]][Hash[to]] = rate;
        }
        floyd();
        bool flag = 0;
        for (int i=0; i<cnt; ++i)
            if (grid[i][i] > 1.0) {
                printf("Case %d: Yesn",times++);
                flag = 1;
                break;
            }
        if (!flag)
            printf("Case %d: Non",times++);
    }
    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
#include <iostream>
#include <string.h>
#include <map>

using namespace std;
const int maxn = 30;
const int inf = 0x3f3f3f3f;

int grid[maxn][maxn];
int n,k;

void init() {
    memset(grid,inf,sizeof grid);
    for (int i=1; i<30; i++)
        grid[i][i] = 0;
}
void floyd() {
    for (int k=1; k<=n; ++k)
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j)
                grid[i][j] = min(grid[i][j],grid[i][k]+grid[k][j]);
}
int main() {
    //freopen("1.in","r",stdin);
    init();
    cin >> n >> k;
    for (int i=1; i<=n; i++) {
        int temp; cin >> temp;
        if (i != n)
            grid[i][i+1] = grid[i+1][i] = temp;
        else grid[i][1] = grid[1][i] = temp;
    }
    char a,b;
    for (int i=1; i<=k; ++i) {
        char a,b; int from,to,time;
        scanf("n%c %c %d",&a,&b,&time);
        from = a - 'A' + 1; to = b - 'A' + 1;
        //cout << "from= " << from << "  to=" << to << endl;
        if (grid[from][to] == inf)
            grid[from][to] = grid[to][from] = 0;
        grid[from][to] = grid[to][from] = max(time,grid[from][to]);
    }
    floyd();
    scanf("n%c %c",&a,&b);
    printf("%dn",grid[a-'A'+1][b-'A'+1]);
    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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 305;
const int inf = 0x3f3f3f3f;

int n,m;
int grid[maxn][maxn],dp[maxn][maxn];

void floyd() {
    for (int k=1; k<=n; ++k)
        for (int i=1; i<=n; ++i) {
            if (grid[i][k]!=inf && i!=k){
                for (int j=1; j<=n; ++j) {
                    if (k==j || i==j) continue;
                    if (grid[i][j]>grid[i][k]+grid[k][j]) {
                        grid[i][j] = grid[i][k]+grid[k][j];
                        dp[i][j] = dp[i][k] + dp[k][j] - 1;
                    } else if (grid[i][j]==grid[i][k]+grid[k][j] &&
                            dp[i][j]<dp[i][k]+dp[k][j])
                        dp[i][j] = dp[i][k] + dp[k][j] - 1;
                }
            }
        }
}
void init() {
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            grid[i][j] = inf;
            dp[i][j] = 2;
        }
        dp[i][i] = 1;
        grid[i][i] = 0;
    }
}
int findThesame(int& s1,int& e1,int& s2,int& e2) {
    int ans = 0;
    if (grid[s1][e1]==inf || grid[s2][e2]==inf) return ans;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
            if (grid[s1][i]+grid[i][j]+grid[j][e1]==grid[s1][e1]
                    && grid[s2][i]+grid[i][j]+grid[j][e2]==grid[s2][e2])
                ans = max(ans,dp[i][j]);
    return ans;
}
int main() {
    //freopen("1.in","r",stdin);
    while (scanf("%d%d",&n,&m)!=EOF && (n+m)) {
        init();
        int a,b,time;
        for (int i=1; i<=m; ++i) {
            scanf("%d%d%d",&a,&b,&time);
            grid[a][b] = grid[b][a] = min(time,grid[a][b]);
        }
        floyd();
        int s1,e1,s2,e2;
        scanf("%d%d%d%d",&s1,&e1,&s2,&e2);
        printf("%dn",findThesame(s1,e1,s2,e2));
    }
    return 0;
}