jskim2023   3년 전

일단 예제는 돌아가는데

어디쯤에서 날지 아직도 모르겟습니다...후..



#include <iostream>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <list>
#include <algorithm>
using namespace std;

#define INF 2147483647;

typedef struct A {
public:
int v, w;
A(int vv, int ww) { v = vv; w = ww; }
};

int D[20001];
int V, E, K;
int u, v, w;
vector<int> S;

vector<A> clist[20001];
vector<int> Q;

int main() {
FILE * file = fopen("data.txt", "r");

fscanf(file,"%d %d", &V, &E);
fscanf(file, "%d", &K);
for (int i = 1; i <= V; i++)
Q.push_back(i);

for (int i = 0; i <= V; i++)
D[i] = INF;

for (int i = 1; i <= E; i++) {
fscanf(file, "%d %d %d", &u, &v, &w);
clist[u].push_back(A(v, w));
}

vector<int>::iterator iter;
int min;
int n = K;
D[K] = 0;

while (!Q.empty()) { // 매번 D갱신하고, 큐에있는것들 다 탐색이 끝나야해
//최소값 찾고,S에 없는거 찾음 그값을 q에서 없에고,  그거와 연결된것들로 값갱신

min = INF;
int cur;
for (int i = 0; i < Q.size(); i++) {

if (D[Q[i]] <min) {
min = D[Q[i]];
n = i;
}

}
cur = Q[n];
Q.erase(Q.begin()+n);
S.push_back(cur);

for (int i = 0; i < clist[cur].size(); i++) { // 작은 경로 발견하면,
//경로가없거나, i,n이 달를때, 
int z = D[cur] + clist[cur][i].w;

if (D[clist[cur][i].v] == 2147483647)//한번도 갱신안된거면 갱신해줘
D[clist[cur][i].v] = z;
else if (z < D[clist[cur][i].v])//기존의 값이 있고, 기존값보다 n까지값하고 n에서 i까지의값이더적ㅇ면 갱신
D[clist[cur][i].v] = z;

}

}
D[K] = 0;

for (int i = 1; i <= V; i++) {
if (D[i] == 2147483647)
cout << "INF" << endl;
else
cout << D[i] << endl;
}

return 0;
}

moonhi123   3년 전

무슨 문제인지 알아야 답변을 해드릴 수 있습니다.

그리고 질문 작성하실때에는 코드는 제일 아래에 소스코드 붙여넣는 곳이 있으니 거기에 붙여넣어 주세요.

자세한 내용은 이곳을 참고하시기 바랍니다.

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