글 읽기 - 특정한 최단경로 문제 왜 틀린지 모르겠습니다.

smu201111192 7년 전 0

왜 틀린지 잘모르겠습니다.

예제케이스와 몇가지테스트케이스를 직접 만들어서 돌려본결과 잘 돌아가는데

어느 부분이 잘못된걸까요.

소스를 간략하게 설명하자면

다익스트라에서 프라이어티큐에 <거리,버텍스>만 집어넣는것이아니고 문제에서 주어진 버텍스를

방문했는지를 <거리,버텍스,상태> 이런식으로 집어넣고 결과적으로

dist[n][3]=문제에서 주어진 두버텍스를 모두 방문한후 n까지의 최단거리를 출력해줍니다.

#include <iostream>
#include <vector>
#include <queue>
#define mp make_pair
using namespace std;
long long dist[801][4]={0,},v,u,n,m;
//dist[801][4]->하나도 안방문 0 u방문시 상태 1 v 방문시 상태 2 모두 방문 3 
struct edge{
    long long to,cost;
    edge(long long to,long long cost){
        this->to=to;
        this->cost=cost;
    }
    edge(){}
};
vector<vector<edge> > adj;
long long dy(long long here){
    priority_queue<pair<long long,pair<long long,long long> > > q;
    for(long long i=0;i<801;i++)
        for(long long j=0;j<4;j++)
            dist[i][j]=1e9;
    long long state=0;
    if(here==u)state=1;
    else if(here==v)state=2;
    dist[here][state]=0;
    q.push(mp(0,mp(1,state)));
    while(!q.empty()){
        long long here=q.top().second.first;
        long long cost=-q.top().first;
        long long s=q.top().second.second;
        q.pop();
        if(dist[here][s]<cost)
            continue;
        for(long long i=0;i<adj[here].size();i++){
            long long there=adj[here][i].to;
            long long c=adj[here][i].cost;
            long long temp=s;
            //printf("not Change:%d\n",temp);
            if(temp==0){
                if(there==u)temp=1;
                else if(there==v)temp=2;
            }
            else if(temp==1){
                if(there==v)temp=3;
            }
            else if(temp==2){
                if(there==u)temp=3;
            }
            //printf("Change:%d\n",temp);
            if(cost+c<dist[there][temp]){
                long long newDist=cost+c;
                dist[there][temp]=newDist;
                q.push(mp(-newDist,mp(there,temp)));
                //printf("dist[%d][%d]=%d+%d\n",there,temp,cost,c);
            }
        }
    }
    return dist[n][3];
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    adj.resize(n+1);
    for(long long i=0;i<m;i++){
        long long from,to,cost;
        cin>>from>>to>>cost;
        adj[from].push_back(edge(to,cost));
        adj[to].push_back(edge(from,cost));
    }
    cin>>u>>v;
    long long ans=dy(1);
    cout<<ans;
    return 0;
}

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

문제

문제

출처

ICPC

특정한 최단경로 문제 왜 틀린지 모르겠습니다.

smu201111192 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말