Wormholes

In the year 2163, wormholes were discovered. A wormhole is a subspace tunnelthrough space and time connecting two star systems. Wormholes have a fewpeculiar properties:

• Wormholes are one-way only.

• The time it takes to travel through a wormhole is negligible.

• A wormhole has two end points, each situated in a star system.

• A star system may have more than one wormhole end point within its boundaries.

• For some unknown reason, starting from our solar system, it is always possible to end up in any star system by following a sequence of wormholes (maybe Earth is the centre of the universe).

• Between any pair of star systems, there is at most one wormhole in either direction.

• There are no wormholes with both end points in the same star system.

All wormholes have a constant time difference between their end points. Forexample, a specific wormhole may cause the person travelling through it toend up 15 years in the future. Another wormhole may cause the person to endup 42 years in the past.

A brilliant physicist, living on earth, wants to use wormholes to study theBig Bang. Since warp drive has not been invented yet, it is not possible forher to travel from one star system to another one directly. This can be done using wormholes, of course.

The scientist wants to reach a cycle of wormholes somewhere in the universethat causes her to end up in the past. By travelling along this cycle a lotof times, the scientist is able to go back as far in time as necessary toreach the beginning of the universe and see the Big Bang with herown eyes. Write a program to find out whether such a cycle exists.

Input 

The input file starts with a line containing the number of cases c to beanalysed. Each case starts with a line with two numbers n and m . Theseindicate the number of star systems ()and the number ofwormholes (). The star systems are numbered from 0 (our solarsystem) through n-1 . For each wormhole a line containing three integernumbers x, y and t is given. These numbers indicate that this wormholeallows someone to travel from the star system numbered x to the star systemnumbered y, thereby ending up t ()years in the future.

Output 

The output consists of c lines, one line for each case, containing the wordpossible if it is indeed possible to go back in time indefinitely, or not possible if this is not possible with the given set of star systems andwormholes.

Sample Input 

23 30 1 10001 2 152 1 -424 40 1 101 2 202 3 303 0 -60

Sample Output 

possiblenot possible

---

用 SPFA 檢查

當某點進入 Queue 的次數多於 n 次時, 即有負環

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
typedef struct {
    int to, v;
} Arc;
typedef vector<Arc>::iterator it;
vector<Arc> link[1000];
bool used[1000];
int dis[1000], inQu[1000];
int checkNegCycle(int n, int st) {
    int i;
    queue<int> Q;
    memset(used, 0, n);
    memset(inQu, 0, 4*n);
    memset(dis, 127, 4*n);
    for(it i = link[st].begin(); i != link[st].end(); i++) {
        if(dis[i->to] > i->v) {
            dis[i->to] = i->v;
            if(!used[i->to]) {
                used[i->to] = true;
                Q.push(i->to);
                inQu[i->to]++;
            }
        }
    }
    int tv;
    while(!Q.empty()) {
        tv = Q.front();
        Q.pop();
        used[tv] = false;
        for(it i = link[tv].begin(); i != link[tv].end(); i++) {
            if(dis[i->to] > dis[tv] + i->v) {
                dis[i->to] = dis[tv] + i->v;
                if(!used[i->to]) {
                    used[i->to] = true;
                    Q.push(i->to);
                    inQu[i->to]++;
                }
                if(dis[st] < 0 || inQu[i->to] >= n)
                    return 1;
            }
        }
    }
    return 0;
}
int main() {
    int t, n, m, i;
    int x, y, v;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++) {
            link[i].clear();
        }
        Arc arc;
        while(m--) {
            scanf("%d %d %d", &x, &y, &v);
            arc.to = y, arc.v = v;
            link[x].push_back(arc);
        }
        int find = 0;
        for(i = 0; i < n; i++) {
            find = checkNegCycle(n, i);
            if(find)
                break;
        }
        if(find == 1)
            puts("possible");
        else
            puts("not possible");
    }
    return 0;
}