Pat 1003 甲级

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <cstdio>

#include <cassert>

using namespace std;

#define N 505

int a[N];

long long mat[N][N], cnt[N][N], han[N][N];

int main() {

    int n, m, s, e;

    while (4 == scanf("%d%d%d%d", &n, &m, &s, &e)) {

        for (int i = ; i < n; ++i) {

            scanf("%d", a + i);

        }

        memset(mat, -, sizeof mat);

        memset(cnt, , sizeof cnt);

        memset(han, , sizeof han);

        while (m--) {

            int x, y, z;

            scanf("%d%d%d", &x, &y, &z);

            assert(!cnt[x][y]);

            mat[x][y] = mat[y][x] = z;

            cnt[x][y]++;

            cnt[y][x]++;

            han[x][y] = a[y];

            han[y][x] = a[x];

        }

        for (int i = ; i < n; ++i) {

            for (int j = ; j < n; ++j) {

                if (!cnt[j][i])continue;

                for (int k = ; k < n; ++k) {

                    if (!cnt[i][k])continue;

                    if (!cnt[j][k] || mat[j][k] > mat[j][i] + mat[i][k]) {

                        mat[j][k] = mat[j][i] + mat[i][k];

                        cnt[j][k] = cnt[j][i] * cnt[i][k];

                        han[j][k] = han[j][i] + han[i][k];

                    } else if (mat[j][k] == mat[j][i] + mat[i][k]) {

                        cnt[j][k] += cnt[j][i] * cnt[i][k];

                        han[j][k] = max(han[j][k], han[j][i] + han[i][k]);

                    }

                }

            }

        }

        if (s == e) {

            cout << 1 << ' ' << a[s] << endl;

        } else {

            cout << cnt[s][e] << ' ' << a[s] + han[s][e] << endl;

        }

    }

    return 0;

}

/*

5 6 0 2

1 2 1 5 3

0 1 1

0 2 2

0 3 1

1 2 1

2 4 1

3 4 1

 */
巴特西

Pat 1003 甲级

最新文章

热门文章
