LightOJ - Instant View of Big Bang(Spfa&DFS)

题目链接:http://lightoj.com/volume_showproblem.php?problem=1108
Time Limit: 2 second(s) Memory Limit: 32 MB

Problem Description

Have you forgotten about wormholes? Oh my god! Ok, let me explain again.

A wormhole is a subspace tunnel through space and time connecting two star systems. Wormholes have a few peculiar properties:

1. Wormholes are one-way only.
2. The time it takes to travel through a wormhole is negligible.
3. A wormhole has two end points, each situated in a star system.
4. A star system may have more than one wormhole end point within its boundaries.
5. Between any pair of star systems, there is at most one wormhole in each direction.
6. There are no wormholes with both end points in the same star system.

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

A brilliant physicist wants to use wormholes to study the Big Bang. Since warp drive has not been invented yet, it is not possible for her to travel from one star system to another one directly. Thiscan be done using wormholes, of course.

The scientist can start her journey from any star system. Then she wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past. By traveling along this cycle a lot of times, the scientist is able to go back as far in time as necessary to reach the beginning of the universe and see the Big Bang with her own eyes. Write a program to help her to find such star systems where she can start her journey.

Input

Input starts with an integer T (≤ 125), denoting the number of test cases.

Each case starts with a blank line. The next line contains two numbers n and m . These indicate the number of star systems (1 ≤ n ≤ 1000) and the number of wormholes (0 ≤ m ≤ 2000). The star systems are numbered from 0 to n-1. For each wormhole a line containing three integer numbers x, y and t is given. These numbers indicate that this wormhole allows someone to travel from the star system numbered x to the star system numbered y, thereby ending up t (-1000 ≤ t ≤ 1000) years in the future or past, a negative integer denotes past, positive integer denotes future.

Output

For each case, print the case number first. Then print the star systems (in ascending order) where she can start her journey. If no such star system is found, print 'impossible'.

Sample Input

2 

3 3
0 1 1000
1 2 15
2 1 -42 

4 4
0 1 10
1 2 20
2 3 30
3 0 -60

Output for Sample Input

Case 1: 0 1 2
Case 2: impossible  

Problem solving report:

Description: 给你一个有向图，问你是否存在负环，如果有负环，就把可以形成负环的起点输出出来，如果没有的话输出 'impossible'。
Problem solving: 正向建边可以找出负环上的边，如果反向建边的话就可以找到负环可以到哪些点，也就是负环的起点。
反向建图，负环是不会变的，只不过是负环的方向换了下，原来能到负环的点变成了现在负环能到的点，求出负环然后深搜标记负环能到的点。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int inf = 0x3f3f3f3f;
struct edge {
    int u, v, w;
    edge() {}
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
}e[MAXN << 1];
int cnt, n;
bool vis[MAXN], visp[MAXN];
int f[MAXN], inq[MAXN], dis[MAXN];
void Add(int u, int v, int w) {
    e[++cnt] = edge(f[u], v, w);
    f[u] = cnt;
}
void init() {
    cnt = 0;
    memset(f, -1, sizeof(f));
    memset(inq, 0, sizeof(inq));
    memset(vis, 0, sizeof(vis));
    memset(visp, 0, sizeof(visp));
    memset(dis, 0, sizeof(dis));
}
void DFS(int u) {
    visp[u] = true;
    for (int i = f[u]; ~i; i = e[i].u)
        if (!visp[e[i].v])
            DFS(e[i].v);
}
void Spfa(int s) {
    queue <int> Q;
    for (int i = 0; i < n; i++)
        Q.push(i);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for (int i = f[u]; ~i; i = e[i].u) {
            int v = e[i].v;
            if (visp[v])
                 continue;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = true;
                    if (++inq[v] >= n)
                        DFS(v);
                }
            }
        }
    }
}
int main() {
    int t, q, m, u, v, w, kase = 0;
    scanf("%d", &t);
    while (t--) {
        init();
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            Add(v, u, w);
        }
        Spfa(0);
        int tmp = 0;
        printf("Case %d:", ++kase);
        for (int i = 0; i < n; i++) {
            if (visp[i]) {
                tmp = 1;
                printf(" %d", i);
            }
        }
        if (!tmp)
            printf(" impossible");
        printf("\n");
    }
    return 0;
}