2013-team5/andrew/13/E

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <vector>
#include <queue>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 2000 + 10;
const long long inf = 1ll<<62;

LL grid[MAXN][MAXN];
vector<int> G[MAXN];
vector<LL> W[MAXN];
LL dis[MAXN];
bool vis[MAXN], mark[MAXN], path[MAXN];
int pre[MAXN];
int N, M, S;
LL lower;

void dfs(int u) {
    mark[u] = 1;
    for (int i = 0; i < (int)G[u].size(); ++ i) {
        int v = G[u][i];
        if (mark[v]) continue;
        dfs(v);
    }
}

int times[MAXN];

void spfa() {
    queue<int> Q;
    while (!Q.empty()) Q.pop();
    for (int i = 0; i < N; ++ i) {
        dis[i] = inf;
        vis[i] = 0;
        times[i] = 0;
    }
    if (mark[S]) return;
    dis[S] = 0; vis[S] = 1; Q.push(S); times[S] = 1;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        if (times[u] > N || dis[u] < lower) {
            if (!mark[u]) dfs(u);
            continue;
        }
        vis[u] = 0;
        for (int i = 0; i < (int)G[u].size(); ++ i) {
            int v = G[u][i];
            LL w = W[u][i];
            if (mark[v]) continue;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    times[v] ++;
                    //assert(times[v] <= N);
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}

int main() {
    freopen("path.in", "r", stdin);
    freopen("path.out", "w", stdout);
    scanf("%d%d%d", &N, &M, &S); S --;
    for (int i = 0; i < N; ++ i) {
        for (int j = 0; j < N; ++ j)
            grid[i][j] = inf;
    }
    for (int i = 0; i < N; ++ i) {
        G[i].clear();
        W[i].clear();
    }
    for (int i = 0; i < M; ++ i) {
        int x, y;
        LL z;
        scanf("%d%d%I64d", &x, &y, &z);
        x --; y --;
        grid[x][y] = min(grid[x][y], z);
    }
    lower = 0;
    for (int i = 0; i < N; ++ i) {
        for (int j = 0; j < N; ++ j) {
            if (grid[i][j] == inf) continue;
            if (grid[i][j] < 0) lower += grid[i][j];
            G[i].push_back(j);
            W[i].push_back(grid[i][j]);
        }
    }
    memset(vis, 0, sizeof(vis));
    memset(mark, 0, sizeof(mark));
    memset(path, 0, sizeof(path));
    spfa();
    for (int i = 0; i < N; ++ i) {
        if (mark[i]) puts("-");
        else {
            if (dis[i] == inf) puts("*");
            else printf("%I64d\n", dis[i]);
        }
    }
    fclose(stdin); fclose(stdout);
    return 0;
}
}}}

#include <vector>
#include <queue>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 2000 + 10;
const long long inf = 1ll<<62;
LL grid[MAXN][MAXN];
vector<int> G[MAXN];
vector<LL> W[MAXN];
LL dis[MAXN];
bool vis[MAXN], mark[MAXN], path[MAXN];
int pre[MAXN];
int N, M, S;
LL lower;
void dfs(int u) {
    mark[u] = 1;
    for (int i = 0; i < (int)G[u].size(); ++ i) {
        int v = G[u][i];
        if (mark[v]) continue;
        dfs(v);
    }
}
int times[MAXN];
void spfa() {
    queue<int> Q;
    while (!Q.empty()) Q.pop();
    for (int i = 0; i < N; ++ i) {
        dis[i] = inf;
        vis[i] = 0;
        times[i] = 0;
    }
    if (mark[S]) return;
    dis[S] = 0; vis[S] = 1; Q.push(S); times[S] = 1;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        if (times[u] > N || dis[u] < lower) {
            if (!mark[u]) dfs(u);
            continue;
        }
        vis[u] = 0;
        for (int i = 0; i < (int)G[u].size(); ++ i) {
            int v = G[u][i];
            LL w = W[u][i];
            if (mark[v]) continue;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    times[v] ++;
                    //assert(times[v] <= N);
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main() {
    freopen("path.in", "r", stdin);
    freopen("path.out", "w", stdout);
    scanf("%d%d%d", &N, &M, &S); S --;
    for (int i = 0; i < N; ++ i) {
        for (int j = 0; j < N; ++ j)
            grid[i][j] = inf;
    }
    for (int i = 0; i < N; ++ i) {
        G[i].clear();
        W[i].clear();
    }
    for (int i = 0; i < M; ++ i) {
        int x, y;
        LL z;
        scanf("%d%d%I64d", &x, &y, &z);
        x --; y --;
        grid[x][y] = min(grid[x][y], z);
    }
    lower = 0;
    for (int i = 0; i < N; ++ i) {
        for (int j = 0; j < N; ++ j) {
            if (grid[i][j] == inf) continue;
            if (grid[i][j] < 0) lower += grid[i][j];
            G[i].push_back(j);
            W[i].push_back(grid[i][j]);
        }
    }
    memset(vis, 0, sizeof(vis));
    memset(mark, 0, sizeof(mark));
    memset(path, 0, sizeof(path));
    spfa();
    for (int i = 0; i < N; ++ i) {
        if (mark[i]) puts("-");
        else {
            if (dis[i] == inf) puts("*");
            else printf("%I64d\n", dis[i]);
        }
    }
    fclose(stdin); fclose(stdout);
    return 0;
}