글 읽기 - 다이스트라를 3번 사용하여 풀었으나, 틀렸습니다... 반례가 있을가요?

wjd86347 4년 전 1

다이스트라를 3번 사용하여 풀려고 하였으나, 테스트케이스, 게시판에 있는 반례는 되지만 틀립니다....

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

struct edge
{
    int next;
    int cost;
};
vector<edge> v[801];
int n,E,s,e,c;
int arr[3]={1,0,0};
int dist[3][801];
int INT_MAX=3*800*1000+1;

void solv()
{
    int here,there,here_cost,there_cost;
    for(int k=0;k<3;k++)
    {
        dist[k][arr[k]]=0;
        priority_queue<pair<int,int>> pq;
        pq.push({0,arr[k]});
        while(!pq.empty())
        {
            here_cost=-pq.top().first;
            here=pq.top().second;
            pq.pop();
            if(dist[k][here]<here_cost) continue;
            for(int i=0;i<v[here].size();i++)
            {
                there=v[here][i].next;
                there_cost=here_cost+v[here][i].cost;
                if(dist[k][there]>there_cost)
                {
                    dist[k][there]=there_cost;
                    pq.push({-there_cost,there});
                }
            } 
        }
    }
}

int main()
{   
    scanf("%d%d",&n,&E);
    while(E--)
    {
        scanf("%d%d%d",&s,&e,&c);
        v[s].push_back({e,c});
        v[e].push_back({s,c});
    }
    scanf("%d%d",arr+1,arr+2);
    fill(&dist[0][0],&dist[2][800],3*800*1000+1);
    solv();
    int ans = min(dist[0][arr[1]]+dist[1][arr[2]]+dist[2][n],dist[0][arr[2]]+dist[2][arr[1]]+dist[1][n]);
    printf("%d\n",(ans>=3*800*1000+1)?-1:ans);
    return 0;
}

wjd86347 4년 전 0

fill함수가 왜인지 모르겠지만 초기화가 잘 안되고 있던것같습니다. 2중 포문으로 초기화를 해주니 맞네요...

djm03178 4년 전 2

fill은 두 번째 인자의 직전 원소까지만 초기화합니다.

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

문제

문제

출처

ICPC

다이스트라를 3번 사용하여 풀었으나, 틀렸습니다... 반례가 있을가요?

wjd86347 4년 전 1

wjd86347 4년 전 0

djm03178 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말