题目地址:http://poj.org/problem?id=3259

题目大意

FJ有$F$块田(实际上就是$F$组数据),每块田有$1 \to N$块区域。有$M$条路径和$W$个虫洞。

给出$M$条双向路径,连接$S\leftrightarrow E$的双向路径区域,需要$T$的时间去通过。然而两个区域之间可以有多条路径。

其次给出$W$个虫洞路径,连接$S \to E$的单向路径区域,从虫洞中$S$穿到$E$可以回到时间$T$之前。

FJ的问题,是否能在他出发之前回到出发点?

思路

刚开始一看,最多500个节点,就考虑用$邻接矩阵+floyd$算法,在处理虫洞的时候将T赋值为$d[s][e]=-T$,将每个d初始化为$INF$(包括$d[i][i]$),$floyd$后遍历$d[i][i]$看看有没有负数(回到起点最短路为负数,可以在出发之前回到起点,符合要求),有的话就输出YES。然后$WA$了。。原来这题两个节点可能有重边= =处理了一下重边($d[s][e]=min(d[s][e],T)$),超时了= =

考虑到$Bellman\_Ford$可以处理负边,这题只要判断有没有负圈即可。97ms通过。

期间了解到$SPFA$算法,也就是$Bellman\_Ford$的优化版,试了一下,125ms通过= =

AC代码(Bellman_Ford)

/*************************************************************************
    > File Name: 3259.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-11-11 三 22:28:00 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int F, N, M, W; // 农场数,区域数,道路数,虫洞数
struct edge {
    int from, to, cost;
} es[5300];

int d[505];
// int Es;

const int INF = 0x3f3f3f3f;

bool bellman_ford(int s) { // 判断是否有负边
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    int Es = 2*M+W;
    for(int i=1; i<=N-1; ++i)
        for(int j=0; j<Es; ++j) {
            edge e = es[j];
            if(d[e.to] > d[e.from] + e.cost) d[e.to] = d[e.from] + e.cost;
        }
    int flag = true;
    for(int j=0; j<Es; ++j)
        if(d[es[j].to] > d[es[j].from] + es[j].cost) { // 负边判断, 有负边
            flag = false;
            break;
        }
    return flag;
}


void solve() {
    puts(bellman_ford(1)?"NO":"YES");
}

int main()
{
#ifdef Oj
    freopen("3259.in", "r", stdin);
#endif
    scanf("%d", &F);
    int S, E, T;
    while(F--) {
        // Es=0;
        scanf("%d%d%d", &N, &M, &W);
        for(int i=0; i<M; ++i) {
            scanf("%d%d%d", &S, &E, &T);

            es[i].from = es[i+M].to= S; // 双向边
            es[i].to = es[i+M].from = E;
            es[i].cost = es[i+M].cost = T;
        }
        for(int i=0; i<W; ++i) {
            scanf("%d%d%d", &S, &E, &T);

            es[i+2*M].from = S; // 虫洞单向边
            es[i+2*M].to = E;
            es[i+2*M].cost = -T; // 时间倒流, -T
        }
        solve();
    }
    return 0;
}

AC代码(SPFA)

/*************************************************************************
    > File Name: 3259_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-11-12 四 09:38:12 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
struct edge {
    int to, cost;
    edge(int to, int cost) : to(to), cost(cost) {}
};

int V, E; // 节点数,边数
int d[505]; // 单源最短距离
vector<edge> G[505]; // 图, 邻接表
bool vinque[505]; // 判断节点是否已经在队列中
int cnt[505]; // 记录每个节点入队次数,超过V则退出(有负圈)。

bool SPFA(int s) {
    memset(d, 0x3f, sizeof(d));
    memset(vinque, 0, sizeof(vinque));
    memset(cnt, 0, sizeof(cnt));
    d[s] = 0;
    queue<int> que; // 入队,存储SPFA需要松弛计算的节点
    que.push(s);
    vinque[s] = true;
    cnt[s] = 1;
    while(!que.empty()) {
        int from = que.front(); que.pop();
        vinque[from] = false;
         for(int i=0; i<G[from].size(); ++i) {
            edge *t = &G[from][i]; // 据说用指针可以提高寻址速度。。
            if(d[t->to] > d[from] + t->cost) {
                d[t->to] = d[from] + t->cost; // 松弛计算
                if(!vinque[t->to]) { // 该节点未入队,将其入队
                    que.push(t->to);
                    vinque[t->to] = true;
                    ++cnt[t->to]; // 入队次数加一
                    if(cnt[t->to] > V) {
                        // while(!que.empty()) que.pop();
                        return false;
                    }
                }
            }
        }
    }
    return true;
}


void solve() {
    puts(SPFA(1)?"NO":"YES");
}

int main()
{
#ifdef Oj
    freopen("3259.in", "r", stdin);
#endif
    int F; // 农场数
    int M, W; // 区域数,虫洞数
    int S, E, T; // 起点,终点,时间
    scanf("%d", &F);
    while(F--) {
        scanf("%d%d%d", &V, &M, &W);

        for(int i=1; i<=V; ++i) G[i].clear(); // 清空图

        for(int i=0; i<M; ++i) {
            scanf("%d%d%d", &S, &E, &T);
            G[S].push_back(edge(E, T));
            G[E].push_back(edge(S, T));
        }
        for(int i=0; i<W; ++i) {
            scanf("%d%d%d", &S, &E, &T);
            G[S].push_back(edge(E, -T));
        }
        solve();
    }
    return 0;
}