PROMISES 구현 문제 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 첨에 입력받으실때 중복 입력이 있을 수 있어서 최솟값 비교를 해주셔야해요 ㅠㅠ 4년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
rundun159
AOJ 문제 중에 PROMISES문제를 풀고 있는데
제가 짠 코드로 하다가 계속 오답으로 뜨길래
책에 있는 코드로 거의 똑같이 했는데 계속 오답이라고 하네요...ㅠㅠ
floyd 알고리즘 사용하고 나서
각 간선이 추가 될때마다 adj[a][b]와 c 를 비교 해서
조건 확인하고 update하는 방식인데....
왜 틀린걸까요??
언어는 c++입니다
6년 전