[HDOJ1317]XYZZY（SPFA, floyd）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1317

题意：给一张有向的点权图，一个人在起点有初始值100，这个人从一个点到另一个点时要加上对应目标点的权值。问有没有一条路径使得这个人的当前值都是正数的前提下，到达终点。

由于问能不能，考虑一个情况就是有正数环的情况，假如这个环可以到达终点，那么无论如何都可以到达终点。这个可达的状态可以通过floyd来求传递闭包得出。因为相当于是求最长路，那么负环就不必要考虑了。

所以做法就是先floyd求出传递闭包，在基础上做spfa，更新两个点之间的时候要考虑是否可达。

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;

const int maxn = 110;
const int maxm = 10100;
const int inf = 0x7f7f7f;
const int nl = 100;
vector<pii> G[maxn];
bool dp[maxn][maxn];
int vcnt[maxn];
int d[maxn];
queue<int> q;
int n, m;

void floyd() {
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(dp[i][k] && dp[k][j]) {
                    dp[i][j] = 1;
                }
            }
        }
    }
}

bool spfa(int s) {
    memset(vcnt, 0, sizeof(vcnt));
    for(int i = 1; i <= n; i++) d[i] = -inf;
    while(!q.empty()) q.pop();
    q.push(s); d[s] = 100;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        if(vcnt[u] > nl) return dp[u][n];
        for(int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].first, w = G[u][i].second;
            if(dp[u][v] && d[v] < d[u] + w && d[u] + w > 0) {
                d[v] = d[u] + w;
                vcnt[v]++;
                q.push(v);
            }
        }
    }
    return d[n] > 0;
}

int main() {
    // freopen("in", "r", stdin);
    int v, w, m;
    while(~scanf("%d",&n) && ~n) {
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++) {
            G[i].clear();
        }
        for(int u = 1; u <= n; u++) {
            scanf("%d %d", &w, &m);
            while(m--) {
                scanf("%d", &v);
                dp[u][v] = 1;
                G[u].push_back(pii(v, w));
            }
        }
        floyd();
        if(dp[1][n]) {
            if(spfa(1)) puts("winnable");
            else puts("hopeless");
        }
        else puts("hopeless");
        // for(int i = 1; i <= n; i++) printf("%d ", d[i]);
        // printf("
");
    }
    return 0;
}