UVa : 558 (Wormholes)


Title : Wormholes

Link : http://uva.onlinejudge.org/external/5/558.html

Tricky Lines :

  1. starting from our solar system, it is always possible to end up in any star system by following a sequence of wormholes
  2. Between any pair of star systems, there is at most one wormhole in either direction.

Analysis :

  1. Bellman-ford algorithm ( http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/ )

Runtime : 0.040s

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

struct edges
{
    int u;
    int v;
    int w;
} e [2000 + 10];

int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        int n, m;
        scanf ("%d %d", &n, &m);

        for ( int i = 0; i < m; i++ )
            scanf ("%d %d %d", &e [i].u, &e [i].v, &e [i].w);

        int d [1000 + 10];
        for ( int i = 0; i <= n; i++ ) d [i] = INT_MAX;

        d [0] = 0;

        for ( int i = 0; i < n - 1; i++ ) {
            for ( int j = 0; j < m; j++ ) {
                if ( d [e [j].u] + e [j].w < d [e [j].v] )
                    d [e [j].v] = d [e [j].u] + e [j].w;
            }
        }

        bool have_negative_cycle = false;

        for ( int j = 0; j < m; j++ ) {
            if ( d [e [j].u] + e [j].w < d [e [j].v] )
                have_negative_cycle = true;
        }

        if ( have_negative_cycle ) printf ("possible\n");
        else printf ("not possible\n");

    }
	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

3 thoughts on “UVa : 558 (Wormholes)

  1. @Ashley
    i don’t see any error , i’ve compiled it with g++
    can u tell me whats the error it shows

  2. I’m sorry. My mistake. It was my machine error. I have re-installed my compiler. And when I submitted to UVa Online Judge, it was accepted. 🙂

    Thank you for sharing. 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s