hdu 4849 Wow! Such City!(dijstra)

浏览数：23 / 时间：2015年06月09日

题目大意：有N个城市，给定计算两两城市距离的公式，然后求0到1~N-1的城市中，最短路径模掉M的最小值。

解题思路：先根据公式求出距离C矩阵，注意中间连乘3次的可能爆long long，然后用裸的dijstra算法求最短路。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxd = 1005;
const int maxn = maxd * maxd;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int N, M;
ll X[maxn], Y[maxn], Z[maxn];
ll C[maxd][maxd], d[maxd];

void init_distant () {
    for (int i = 1; i < N * N; i++) {
        if (i >= 2) {
            X[i] = (12345 + X[i-1] * 23456 + X[i-2] * 34567 + (X[i-1] * X[i-2] % 5837501) * 45678)  % 5837501;
            Y[i] = (56789 + Y[i-1] * 67890 + Y[i-2] * 78901 + (Y[i-1] * Y[i-2] % 9860381) * 89012)  % 9860381;
        }
        Z[i] = (X[i] * 90123 + Y[i]) % 8475871 + 1;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j)
                C[i][j] = 0;
            else
                C[i][j] = Z[i*N+j];
        }
    }
}

ll dijstra () {
    int v[maxd];
    memset(v, 0, sizeof(v));
    for (int i = 0; i < N; i++)
        d[i] = INF;
    d[0] = 0;

    ll ans = INF;
    for (int i = 0; i < N; i++) {

        int u = 0;
        ll dis = INF;
        for (int j = 0; j < N; j++) {
            if (d[j] < dis && v[j] == 0) {
                u = j;
                dis = d[j];
            }
        }

        v[u] = 1;
        if (d[u] % M < ans && u)
            ans = d[u] % M;

        for (int j = 0; j < N; j++) {
            if (d[u] + C[u][j] < d[j])
                d[j] = d[u] + C[u][j];
        }
    }
    return ans;
}

int main () {
    while (scanf("%d%d%lld%lld%lld%lld", &N, &M, &X[0], &X[1], &Y[0], &Y[1]) == 6) {
        init_distant();
        printf("%lld\n", dijstra());
    }
    /*
    while (cin >> N >> M >> X[0] >> X[1] >> Y[0] >> Y[1]) {
        init_distant();
        cout << dijstra() << endl;
    }
    */
    return 0;
}