다이나믹 프로그래밍

트리 맵이 주어짐. 출발 노드에서 모든 노드로 가는 데의 최소 비용을 구함. 음의 간선x

2차원 dp로 푼다

1916번: 최소비용 구하기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

int visit[1001];
int N,M;
int dig[1001][1001];
int d[1001];
int start,end;

int getsmall(){ //visit 체크되지 않은 수 중 가장 작은 수 찾기 
	int min = 99999999;
	int index;
	for(int i=1;i<=N;i++){
		if(!visit[i]&&d[i]<min){
			min = d[i];
			index = i;
		}
	}
	return index;
}
void print(int n){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dig[i][j] !=99999999){
					printf("%d ",dig[i][j]);
			}else{
				printf("-1 ");
			}
		
		
		}
		printf("\\n");
	}
}
int main(){
	
	scanf("%d %d",&N,&M);
	int t1, t2, t3;
	for(int i=0;i<=N;i++){  //최대로 초기화 , 맵 만들기
		for(int j=0;j<=N;j++){
			dig[i][j]=99999999;
		}
	}
	
	for(int i=0;i<M;i++){ //값 넣어줌 
		scanf("%d %d %d",&t1,&t2,&t3);  //t1 -> t2 t3의 비용 
		dig[t1][t2] =t3<dig[t1][t2]?t3:dig[t1][t2]; //비용이 겹칠 때 최소비용으로 업뎃
		
	}
	scanf("%d %d",&start,&end);
	visit[start]=1; //이미 잡은 기준 노드 =1 로 표시
	for(int i=1;i<=N;i++){
		dig[i][i]=0;
		
	}
	
	for(int i=1;i<=N;i++){ 
		d[i]= dig[start][i];
		
	}

	for(int i=1;i<=N-1;i++){
		int x = getsmall();  //업데이트 해줄 노드 구하기 
//		printf("%d\\n",x);
		visit[x]= true;
		for(int j=1;j<=N;j++){ // 1~N까지 노드 순환 
			if(!visit[j]){ // 
				if(d[x]+dig[x][j]<d[j]){
					d[j] = d[x]+dig[x][j];
					
				}
			
			}
		}
//		for(int i=1;i<=N;i++){
//			printf("%d ",d[i]);
//		}
//		printf("\\n");
	}
	printf("%d",d[end]);
}

1753번: 최단경로

최단경로이지선

• 배열 저장 stl 사용

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

int dig[20001][2];
int d[20001];
int visit[20001];
int V, E, start;

int getSmall() {
    int min = 11;
    int index;
    for (int i = 1; i <= V; i++) {
        if (!visit[i] && d[i] < min) {
            min = d[i];
            index = i;
        }
    }
    return index;
}

void print() {
    for (int j = start; j <= V; j++) {
        if (d[j] != 11) {
            printf("%d\\n", d[j]);
        } else {
            printf("INF\\n");
        }
    }
    printf("\\n");
}

int main() {

    scanf("%d %d", &V, &E);
    int t1, t2, t3;
    for (int i = 0; i <= V; i++) { 
        for (int j = 0; j <= V; j++) {
            dig[i][j] = 11;
        }
    }

    scanf("%d", &start);
    visit[start] = 1; 
    for (int i = 1; i <= V; i++) {
        dig[i][i] = 0;
    }

    for (int i = 0; i < E; i++) { 
        scanf("%d %d %d", &t1, &t2, &t3); 
        dig[t1][t2] = t3 < dig[t1][t2] ? t3 : dig[t1][t2]; 
    }

    for (int i = 1; i <= V; i++) {
        d[i] = dig[start][i];
    }

    for (int i = 1; i <= V-1; i++) {
        int x = getSmall();
        visit[x] = 1;
        for (int j = 1; j <= V; j++) { 
            if (!visit[j]) {
                if (d[x] != 11 && dig[x][j] != 11 && d[x] + dig[x][j] < d[j]) {
                    d[j] = d[x] + dig[x][j];
                }
            }
        }
    }
    print();
    return 0;
}

1504번: 특정한 최단 경로

특정한최단경로이채연

다음주까지 - 목요일 5시

• [ ] 문제 풀어오기