1) 2차원 배열
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include<cstdio> #include<algorithm> #include<vector> #include<utility> #include<cstring> using namespace std; #define INF 100000000 int arr[502][502]; int d[502]; bool visited[502]; int n,m,w,from,to,weight; bool flag; void bellman(int x){ for(int i=1; i<=n; i++) d[i]=INF; d[x]=0; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ for(int k=1; k<=n; k++){ if(d[j]!=INF && d[k]>d[j]+arr[j][k]){ d[k]=d[j]+arr[j][k]; visited[j]=true; visited[k]=true; if(i==n) flag=true; } } } } } int main(void){ int t; scanf("%d", &t); while(t--){ scanf("%d %d %d", &n, &m, &w); // 초기화 for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) arr[i][j]=INF; for(int i=1; i<=n; i++) d[i]=INF; // 도로 입력 for(int i=0; i<m; i++){ scanf("%d %d %d", &from, &to, &weight); if(arr[from][to]==INF){ arr[from][to]=weight; arr[to][from]=weight; } else { if(arr[from][to]>weight){ arr[from][to]=weight; arr[to][from]=weight; } } } // 웜홀 입력받기 for(int i=0; i<w; i++){ scanf("%d %d %d", &from, &to, &weight); arr[from][to]=-weight; } flag=false; for(int i=1; i<=n; i++){ if(!visited[i]) bellman(i); } if(flag) printf("YES\n"); else printf("NO\n"); memset(visited,false,sizeof(visited)); } return 0; } | cs |
2) 벡터로
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<cstdio> #include<vector> #include<utility> #include<algorithm> #include<cstring> using namespace std; #define INF 100000000 vector<pair<int,int>> arr[502]; int dist[502]; bool visited[502]; int n,m,w,from,to,weight; bool flag; void bellman(int node){ dist[node]=0; for(int i=1; i<=n; i++){ for(int from=1; from<=n; from++){ for(int to=0; to<arr[from].size(); to++){ int next=arr[from][to].first; int cost=arr[from][to].second; if(dist[from]!=INF && dist[next]>dist[from]+cost){ dist[next]=dist[from]+cost; visited[from]=true; visited[next]=true; if(i==n) flag=true; } } } } } int main(void){ int t; scanf("%d", &t); while(t--){ scanf("%d %d %d", &n, &m, &w); for(int i=0; i<m; i++){ scanf("%d %d %d", &from, &to, &weight); arr[from].push_back(make_pair(to,weight)); arr[to].push_back(make_pair(from,weight)); } for(int i=0; i<w; i++){ scanf("%d %d %d", &from, &to, &weight); arr[from].push_back(make_pair(to,(-1)*weight)); } fill(dist,dist+n+1,INF); flag=false; for(int i=1; i<=n; i++){ if(!visited[i]) bellman(i); } if(flag) printf("YES\n"); else printf("NO\n"); memset(visited,false,sizeof(visited)); for(int i=1; i<=n; i++) arr[i].clear(); } return 0; } | cs |
벡터로 푸는거에서 엄청 많이 틀렸는데 결국엔 초기화 문제였음ㅋ
'백준 2 > 그래프' 카테고리의 다른 글
| [백준 5427] 불 (C++/Python) (0) | 2020.12.08 |
|---|---|
| [백준 14442] 벽 부수고 이동하기 2 (0) | 2020.12.08 |
| [백준 11657] 타임머신 (0) | 2020.12.08 |
| [백준 2589] 보물섬 (0) | 2020.12.08 |
| [백준 10159] 저울 (0) | 2020.12.08 |