7 - 1 원활 한 공사 의 부분 최소 비용 문제 (35 점)

#include
#define MAX 100
#define INFINITY 65535
bool marked[MAX];//      
int pathMar[MAX][MAX];//     
int Dist[MAX];//                

int main()
{
    int n;//   
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
    {
        pathMar[i][j] = INFINITY;//               
    }
    int m = n * (n - 1) / 2;//    
    for(int i = 0; i < m; i ++)
    {
        int a, b, c, d;//         ，  ，    
        scanf("%d%d%d%d", &a, &b, &c, &d);
        if(d == 1)//          
        {
            pathMar[a - 1][b - 1] = pathMar[b - 1][a - 1] = 0;
        }
        else
        {
            pathMar[a - 1][b - 1] = pathMar[b - 1][a - 1] = c;
        }
    }
    //   Dist
     for(int i = 0; i < n; i ++)
     {
         Dist[i] = pathMar[0][i];
     }

     marked[0] = 0;
     Dist[0] = 0;
     //      ，            0
     int sum = 0;
     for(int i = 0; i < n; i ++)
     {
         int minPath = INFINITY;
         int order  = -1;
         for(int j = 0; j < n; j ++)
         {
             if(minPath > Dist[j] && !marked[j])
             {
                 minPath = Dist[j];//             
                 order = j;//               
             }
         }
         //    。  
         marked[order] = true;
         //                      
         if(order != -1)
         {
             sum += minPath;
             for(int j = 1; j < n; j ++)
             {
                 if(Dist[j] > pathMar[order][j] && !marked[j])
                 //                      Dist
                 Dist[j] = pathMar[order][j];

             }
         }

     }
     printf("%d", sum);
     return 0;
}

한 지역 은 도시 교통 상황 에 대한 조 사 를 통 해 기 존의 도시 간 고속도로 에 대한 통계 데 이 터 를 얻 고 '원활 한 공사' 의 목 표를 제시 했다. 전체 지역 의 모든 두 도시 간 에 신속 한 교통 을 실현 할 수 있 도록 하 는 것 이다 (그러나 직접적인 고속도로 가 연결 되 는 것 이 아니 라 서로 간접 적 으로 빠 른 길 을 통 해 도달 하면 된다).현재 도시 도로 통계 표를 얻 었 는데 표 에는 임의의 두 도시 간 에 고속도 로 를 건설 하 는 비용 과 이 도로 가 이미 뚫 렸 는 지 의 상태 가 열거 되 어 있다.지금 당신 이 프로그램 을 작성 하여 전 지역 이 원활 하 게 통 하 는 데 필요 한 최저 원 가 를 계산 해 주 십시오.
입력 형식:
입력 한 첫 줄 에 마을 수 N (1 ≤ N ≤ 100) 을 드 립 니 다.이 어 N (N - 1) / 2 행 은 마을 간 도로 의 원가 와 건설 상태 에 대응 했다. 각 줄 에 4 개의 정 수 를 주 었 는데 각각 두 마을 의 번호 (1 번 에서 N 번 까지) 이다. 이 두 마을 간 도로 의 원가 와 건설 상태 - 1 은 이미 건설 되 었 고 0 은 건설 되 지 않 았 음 을 나타 낸다.
출력 형식:
전 성의 원활 한 수출 에 필요 한 최저 비용.
입력 예시:

4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0

출력 예시:

3