[백준 1865] 웜홀

#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;
}

2) 벡터로

#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;
}

벡터로 푸는거에서 엄청 많이 틀렸는데 결국엔 초기화 문제였음ㅋ