검색어 입력폼

[프로그래밍]최단거리구하기

등록일 2006.01.08 파일확장자 압축파일 (alz) | 가격 1,000원

*해당 문서는 미리보기가 지원되지 않습니다.

소개글

에지에 가중치가 부여된 비방향성 그래프가 주어지고, 출발 정점과 목적지 정점이 주어질 때 출발 정점에서 목적지 정점까지 가는 최단 경로에 있는 에지들의 가중치 합을 계산하여 출력하는 프로그램을 작성하라.
입력파일의 첫째 줄에는 두 정수 n, m이 있는데 n은 그래프에 있는 총 정점의 수를 나타내고, m은 에지의 개수를 나타낸다. 두 번째 줄에는 4개의 정수 s, t1, t2, t3가 있는데 s는 출발 정점, t1, t2, t3는 목적지 정점을 나타낸다. 이어서 m개의 줄에 세 값 i, j, w가 있으며, 각 줄에 있는 이 값 들은 에지의 정보를 나타낸다. 즉, 정점 i와 정점 j에 에지가 존재하며, 그 가중치는 w임을 나타낸다. 그래프에 n개의 정점이 있는 경우 각 정점의 인덱스는 1부터 n까지이다. 그리고 n은 500을 넘지 않는다. 즉, 그래프에 있는 정점의 수는 최대 500개이다.
여러분은 주어진 그래프 정보를 이용하여 출발지 s 로부터 각각의 목적지 t1, t2, t3로 가는 최단 경로를 구하고, 그 최단 경로의 길이를 보여야 한다. 서로 다른 세 목적지까지의 최단경로의 길이를 보일 때 공백 문자를 사이에 삽입하여 구분하도록 한다. 아래 그래프에 대응된 입력과 출력은 다음과 같다.

컴파일 실행환경

비주얼 C++ 6.0

본문내용

#include <iostream.h>
#include <fstream.h>

int shortestPath(int start, int end, int node);
int length[500];
int mark[500];
int inputMatrix[500][500];

int main(void)
{
int node;
int edge;
int start;
int end1;
int end2;
int end3;

int x;
int y;
int z;

int i;
int j;

ifstream fin("1.inp");
ofstream out("1.out");

if(!fin)
return -1;

fin >> node;
fin >> edge;
fin >> start;
fin >> end1;
fin >> end2;
fin >> end3;

for(i=0; i<edge; i++) {
fin >> x;
fin >> y;
fin >> z;
inputMatrix[x-1][y-1] = z;
inputMatrix[y-1][x-1] = z;
}

for(i=0; i< node; i++) {
for(j=0; j< node; j++) {
if (!(inputMatrix[i][j] > 0 && inputMatrix[i][j]<=1000000000))
inputMatrix[i][j] = 1000000000;
}
}

out<<shortestPath(start-1, end1-1, node)<<" ";
out<<shortestPath(start-1, end2-1, node)<<" ";
out<<shortestPath(start-1, end3-1, node);

참고 자료

없음
다운로드 맨위로