PROMISES 구현 문제

  • rundun159
    rundun159

    AOJ 문제 중에 PROMISES문제를 풀고 있는데
    제가 짠 코드로 하다가 계속 오답으로 뜨길래
    책에 있는 코드로 거의 똑같이 했는데 계속 오답이라고 하네요...ㅠㅠ
    floyd 알고리즘 사용하고 나서
    각 간선이 추가 될때마다 adj[a][b]와 c 를 비교 해서
    조건 확인하고 update하는 방식인데....
    왜 틀린걸까요??
    언어는 c++입니다

    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int MAX_V=200;
    int v;
    const int INF=987654321;
    int adj[MAX_V][MAX_V];  //없는 간선은 INF로 초기화
    void initialAdj();
    int main()
    {
        freopen("input.txt", "r", stdin);
        int testCase;cin>>testCase;
        for(int cases=0;cases<testCase;cases++)
        {
            int n,m;cin>>v;cin>>n;cin>>m;
            initialAdj();
            for(int i=0;i<n;i++)
            {
                int a,b,c;cin>>a;cin>>b;cin>>c;
                adj[a][b]=c;
                adj[b][a]=c;
            }
            for(int k=0;k<v;k++)
                for(int i=0;i<v;i++)
                    for(int j=0;j<v;j++)
                        adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j]);
            int sum=0;
            for(int l=0;l<m;l++)
            {
                int a,b,c;cin>>a;cin>>b;cin>>c;
                if(adj[a][b]<=c)
                {
                    sum++;
                    continue;
                }
                else
                {
                    for(int i=0;i<v;i++)
                        for(int j=0;j<v;j++)
                            adj[i][j]=min(adj[i][j],min(adj[i][a]+c+adj[b][j],adj[i][b]+c+adj[a][j]));
                }
            }
            cout<<sum<<endl;
        }
    }
    void initialAdj()
    {
        for(int i=0;i<v;i++)
            for(int j=0;j<v;j++)
                if(i==j)
                    adj[i][j]=0;
                else
                    adj[i][j]=INF;
    }
    

    6년 전
1개의 댓글이 있습니다.
  • akwk777
    akwk777

    첨에 입력받으실때 중복 입력이 있을 수 있어서 최솟값 비교를 해주셔야해요 ㅠㅠ


    4년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.