글 읽기 - 100%에서 틀렸습니다 뜹니다

ptw1046 6년 전 0

다익스트라 알고리즘을 사용해서

목적지, 도착지 순으로

(1,a) (a,b) (b,n)

(1,b) (a,n)

for문을 통해 각각 답을 구합니다.

그래서 1 a b n, 1 b a n 중 작은것을 답으로 하는데

100%에서 오답이 뜨네요.... 무엇이 문제일까요??

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <utility>
using namespace std;

const int Max_V = 1000;
const long INF = 10000000000;
typedef pair<int, int> P;

int main() {
	int n, m; scanf("%d %d", &n, &m);

	vector<P> adj[Max_V];

	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		adj[u - 1].push_back(P(v - 1, w));
		adj[v - 1].push_back(P(u - 1, w));
	}

	int a, b; scanf("%d %d", &a, &b);

	int s[5] = { 0,a-1,b-1,0,a-1 }, e[5] = { a-1,b-1,n - 1,b-1,n-1 };

	int ans[5];

	for (int t = 0; t < 5; t++) {
		long dist[Max_V];
		fill(dist, dist + Max_V, INF);
		bool visit[Max_V] = { 0 };

		priority_queue<P, vector<P>, greater<P>> PQ;

		dist[s[t]] = 0;
		PQ.push(P(0, s[t]));
		while (!PQ.empty()) {
			int cur;
			do {
				cur = PQ.top().second;
				PQ.pop();
			} while (!PQ.empty() && visit[cur]);

			if (visit[cur]) break;

			visit[cur] = true;

			for (auto &p : adj[cur]) {
				int next = p.first, d = p.second;
				if (dist[next] > dist[cur] + d) {
					dist[next] = dist[cur] + d;
					PQ.push(P(dist[next], next));
				}
			}
		}
		ans[t] = dist[e[t]];
	}

	long tot;
	tot =  min(ans[0] + ans[1] + ans[2], ans[3] + ans[4] + ans[1]);
	printf("%lld", tot >= INF ? -1 : tot);
}

kdk8361 6년 전 0

ans가 int네요

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

문제

문제

출처

ICPC

100%에서 틀렸습니다 뜹니다

ptw1046 6년 전 0

kdk8361 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말