글 읽기 - 초기값 설정 문제

gudrbscse 7년 전 0

1번은 테스트 케이스에서 잘 안나오고

2번은 맞앗다고 나옵니다.

둘의 차이를 잘 모르겠습니다.

ㅠㅠ

고수님들의 답변 부탁드립니다

//1번 
#include<iostream>    
#include<vector>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

#define INF 1000000000

int min(int a, int b) {
	if (a > b) return b;
	else return a;
}

int arr[1001][1001];
int d[1001];
bool c[1001];
int main() {
	for (int i = 0; i < 1001; i++)
		for (int j = 0; j < 10001; j++)
			arr[i][j] = INF;
	for (int i = 0; i < 1001; i++)
		d[i] = INF;
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[a][b] = min(arr[a][b], c);
	}
	int start, end;
	cin >> start >> end;
	d[start] = 0;
	for (int k = 0; k < n - 1; k++) {
		int min = INF + 1;
		int minp = -1;
		for (int i = 1; i <= n; i++) {
			if (c[i] == false && min > d[i]) {
				min = d[i];
				minp = i;
			}
		}
		if (minp == -1)
			break;
		c[minp] = true;
		for (int i = 1; i <= n; i++) {
			if (d[i] > d[minp] + arr[minp][i]) {
				d[i] = d[minp] + arr[minp][i];
				cout << i << " " << d[i] << endl;
			}
		}
	}
	cout << d[end] << endl;
	return 0;
}


//2번
#include<iostream>
#include<cstdio>
using namespace std;
int min(int a, int b) {
    if (a > b) return b;
    else return a;
}
int a[1001][1001];
int d[1001];
bool c[1001];
int main() {
    //Dijkstra Algo
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = 1000000000;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        a[x][y] = min(a[x][y], z);
    }
    for (int i = 1; i <= n; i++)
        d[i] = 1000000000;
    int st, ed;
    scanf("%d %d",&st,&ed);
    d[st] = 0;
    for (int k = 0; k < n-1; k++) {
        int min = 100000001;
        int minp = 0;
        for (int i = 1; i <= n; i++) {
            if (c[i] == false && min >d[i]) {
                min = d[i];
                minp = i;
            }
        }
        if (minp == 0) break;
        c[minp] = true;
        for (int i = 1; i <= n; i++) {
            if (d[i] > d[minp] + a[minp][i]) {
                d[i] = d[minp] + a[minp][i];
            }
        }
    }
    printf("%d\n", d[ed]);
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

초기값 설정 문제

gudrbscse 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말