글 읽기 - 1504번 8~9%에서 틀립니다.. 어디가 문제일까요??

iiiiiiillllllli 2년 전 0

다익스트라 알고리즘, 인접 연결리스트를 이용한 그래프 표현 사용했습니다.

질문게시판에 모든 반례를 해봤는데 다 답은 나오는데 틀리네요..

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

두가지 경우 계산해서 하나라도 연결되지 않은 경로라면 -1을 반환하고 아니면 최솟값을 반환하게 하였습니다. 양방향 연결이므로 인접리스트에 둘다 추가해주었습니다.

혹시 오버플로때문인가 싶어서 long long 썻는데도 틀려서 뭐가 문제인지 1도 감이 안옵니다..

뭐가 문제인지 알려주시면 감사하겠습니다!!

#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#define ll long long
#define INF 987654321
#define INT_MAX 2147483647
#define MIN(a, b) ((a) < (b) ? a : b)
#define MAX(a, b) ((a) > (b) ? a : b)
using namespace std;

int v, e;

vector<ll> dijkstra(int src, vector<vector<pair<int, ll>>> &adj)
{
	vector<ll> dist(v + 1, INF);
	dist[src] = 0;
	priority_queue<pair<ll, int>> pq;
	pq.push(make_pair(0, src));
	while (!pq.empty()) {
		ll cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if (dist[here] < cost) continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			ll nextDist = cost + adj[here][i].second;
			if (dist[there] > nextDist) {
				dist[there] = nextDist;
				pq.push(make_pair(-nextDist, there));
			}
		}
	}
	return dist;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    
	cin >> v >> e;
	vector<vector<pair<int, ll>>> adj(v + 1);
	for (int i = 0; i < e; i++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
	}
	int V1, V2;
	cin >> V1 >> V2;
	vector<ll> start = dijkstra(1, adj);
	vector<ll> V1start = dijkstra(V1, adj);
	vector<ll> V2start = dijkstra(V2, adj);

    ll StoV1 = start[V1];
    ll V1toV2 = V1start[V2];
    ll V2toE = V2start[v];

    ll StoV2 = start[V2];
    ll V2toV1 = V2start[V1];
    ll V1toE = V1start[v];

    ll ans1, ans2;
    ans1 = INF;
    ans2 = INF;

    if(StoV1 != INF && V1toV2 != INF && V2toE != INF) 
        ans1 = StoV1 + V1toV2 + V2toE;
    if(StoV2 != INF && V2toV1 != INF && V1toE != INF) 
        ans2 = StoV2 + V2toV1 + V1toE;
    ll ans = MIN(ans1, ans2);
	if (ans == INF)
		cout << -1 << '\n';
	else
		cout << ans << '\n';

    return 0;
}

bluejoyq 2년 전 1

반례 찾았습니다.

입력 :

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
1 4

현재 출력 :

런타임에러

v1이 1이거나 v2가 N인 경우가 고려되지 않은 것 같습니다.

pmn0001 2년 전 1

문제의 조건상 v1 이 1일 수 있고, v2 가 n일 수 있습니다.

iiiiiiillllllli 2년 전 0

@bluejoyq

혹시 컴파일 환경이 어떤지 알수 있을까요? 제 환경에서는 답이 4로 출력되는데 런타임에러가 나는 부분이 어딘지 잘 모르겠네요 ㅜㅜ

iiiiiiillllllli 2년 전 0

아 해결했습니다 ㅜㅜㅜㅜㅜ V1이 1이거나 V2가 N인경우도 다 고려했었는데 계속 틀려서 죽을맛이엇는데 설마 이게 문제인가 싶어서 고치니까 되네요 ㅜㅜ

ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);

위 코드로 fastio 쓰고 있었는데 옛날에 풀었다가 포기한 코드 복붙하다 보니 입력을 scanf로 받아서 cin,cout이랑 섞어쓰고있었네요... 이거 하나땜에 몇시간동안 삽질했네요 흑흑

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

문제

문제

출처

ICPC

1504번 8~9%에서 틀립니다.. 어디가 문제일까요??

iiiiiiillllllli 2년 전 0

bluejoyq 2년 전 1

pmn0001 2년 전 1

iiiiiiillllllli 2년 전 0

iiiiiiillllllli 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말