pku 2983 Is the Information Reliable? 계차 제약

http://poj.org/problem?id=2983
제목: 주어진 두 가지 구속 관계
Precise tip is in the form of  P A B X , means defense station A is X light-years north of defense station B.
Vague tip is in the form of  V A B , means defense station A is in the north of defense station B, at least 1 light-year, but the precise distance is unknown.
d [i] 는 i 와 0 의 거 리 를 나타 내 고 p 관 계 는 x < = d [b] - d [a] < = x 로 표시 할 수 있다.  V 관 계 는 d [b] - d [a] > = 1 로 나 타 낼 수 있다.제약 관계 간소화: P: d [b] - d [a] < = x   d[a] - d[b] <= -c  V: d[a] - d[b] <= -1
최 단 로 를 구하 여 bellman 존재 여 부 를 판단 합 니 다.ford。할 때 memset 로 g 를 초기 화 했 는데 계속 tle 을 제거 한 후에 ac 가 되 었 습 니 다. 앞으로 가능 한 한 스스로 훈 화 를 쓰 고 사고 가 난 것 같 습 니 다.
 

#include <cstdio>

#include <cstring>

#include <iostream>

#define maxn 100007

using namespace std;



struct node

{

    int u,v,w;

}g[maxn*100];

int len;

int n,m,dis[1005];

const int inf = 99999999;



void add(int u,int v,int w)

{

    g[len].u = u;

    g[len].v = v;

    g[len].w = w;

    len++;

}

bool bellman_ford(int s)

{

    int i,j;

    for (i = 1; i <= n; ++i) dis[i] = inf;

    dis[s] = 0;

    for (i = 1; i < n; ++i)

    {

        bool flag = false;

        for (j = 0; j < len; ++j)

        {

            int u = g[j].u,v = g[j].v,w = g[j].w;

            if (dis[v] > dis[u] + w)

            {

                dis[v] = dis[u] + w;

                flag = true;

            }

        }

        if (!flag) return true;

    }

    for (j = 0; j < len; ++j)

    {

        int u = g[j].u,v = g[j].v,w = g[j].w;

        if (dis[v] > dis[u] + w) return false;

    }

    return true;

}

int main()

{

    int i;

    int a,b,c;

    char op[3];

    while (~scanf("%d%d",&n,&m))

    {

        len = 0;

        for (i = 0; i < m; ++i)

        {

            scanf("%s%d%d",op,&a,&b);

            if (op[0] == 'P')

            {

                scanf("%d",&c);

                add(b,a,-c);

                add(a,b,c);

            }

            else

            {

                add(b,a,-1);

            }

        }

        if (bellman_ford(1)) printf("Reliable
");

        else printf("Unreliable
");

    }

    return 0;

}