11721 - Instant View of Big Bang UVa Solution

 #include <bits/stdc++.h>
using namespace std;
int n,m,t,cycle;
struct edge{
    int x,y,t;
};
vector<edge> edges;
vector<vector<int> > adj;
vector<int> vis;
int dfs(int i){
    if(vis[i]!=-1)
        return vis[i];
    vis[i]=0;
    for(int j=0;j<adj[i].size();j++)
        if(dfs(adj[i][j])){
            return vis[i]=1;
        }
    return vis[i]=0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>t;
    int i=1;
    while(i<=t){
        edges.clear();
        cout<<"Case "<<i++<<':';
        cin>>n>>m;
        adj.assign(n+1,vector<int>());
        vis.assign(n+1,-1);
        for(int i=0;i<m;i++){
            edge a;
            cin>>a.y>>a.x>>a.t;
            edges.push_back(a);
            adj[a.y].push_back(a.x);
        }
        for(int i=0;i<n;i++){
            edge a;
            a.x=n;a.y=i;a.t=0;
            edges.push_back(a);
        }
        vector<int> dist(n+1,INT_MAX);
        dist[n]=0;
        int cycle;
        for(int i=0;i<n+1;i++){
            cycle=-1;
            for(int j=0;j<edges.size();j++){
                int x=edges[j].x,y=edges[j].y,t=edges[j].t;
                if(dist[x]!=INT_MAX && dist[x]+t<dist[y]){
                    if(i==n)
                        vis[y]=1;
                    dist[y]=dist[x]+t;
                    cycle=y;
                }
            }
        }
        if(cycle==-1)
            cout<<" impossible"<<'\n';
        else{
            for(int k=0;k<n;k++)
                dfs(k);
            for(int i=0;i<n;i++)
                if(vis[i]==1)
                    cout<<' '<<i;
            cout<<'\n';
        }
    }
}