백준 문제 1504번 특정한 최단 경로 문제풀이 c++

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

문제해석

 

1번 정점에서 N번정점까지의 최단거리는 다익스트라 알고리즘을 사용하면 구할수있다.

그러나 여기선 V1,V2가 주어지고 꼭 이 두점을 지나야 한다는 조건이 붙어있다.

 

맨 처음 이문제를 볼때는 너무 어렵게 생각한 나머지 어떻게 풀지 생각이 안났는데 며칠 지난후 나중에 다시 이 문제를 보니 갑자기 어떻게 풀어야할지 보이길래 어렵게 생각한게 독이 되었단걸 알게되었다.

 

1 -> V1 -> V2 -> N

1 -> V2 -> V1 -> N

 

이 두개의 경로중 더 짧은쪽을 선택하면 된다.

물론 a -> b는 a에서 b까지 최단경로를 의미한다. 

그렇다면 다익스트라함수를 최대 6번 돌리면 충분히 구할 수있다.

중복된것을 제외하여 난 3번을 돌려서 풀었다.

 

코드

 

#define INF 999999999
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
typedef long long int ll;
using namespace std;
ll getsmall();
void dijk(ll start);
void reset();
ll arr[801][801];
ll d[801];
bool visited[801];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    for(ll i=0; i<801; i++)
    {
        for(ll j=0; j<801; j++)
        {
            if(i!=j)
            {
                arr[i][j]=INF;
            }
        }
    }
    ll n,e; cin>>n>>e;
    for(ll i=0; i<e; i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        arr[a][b]=c;
        arr[b][a]=c;
    }
    ll v1,v2; cin>>v1>>v2;
    ll ans[2]={0,0};

    dijk(1);
    ans[0]=ans[0]+d[v1];
    ans[1]=ans[1]+d[v2];
    reset();

    dijk(v1);
    ans[0]=ans[0]+d[v2];
    reset();

    dijk(v2);
    ans[0]=ans[0]+d[n];
    ans[1]=ans[1]+d[v1];
    reset();

    dijk(v1);
    ans[1]=ans[1]+d[n];

    if(min(ans[0],ans[1])>=INF)
    {
        cout<<-1;
    }
    else
    {
        cout<<min(ans[0],ans[1]);
    }
}
ll getsmall(){
    ll mn=INF;
    ll index=0;
    for(ll i=0; i<801; i++)
    {
        if(visited[i]==0&&mn>d[i])
        {
            mn=d[i];
            index=i;
        }
    }
    return index;
}
void dijk(ll start){
    visited[start]=1;
    for(ll i=0; i<801; i++)
    {
        d[i]=arr[start][i];
    }
    for(ll i=0; i<801; i++)
    {
        ll cur=getsmall();
        visited[cur]=1;
        for(ll j=0; j<801; j++)
        {
            if(visited[j]==0)
            {
                if(d[j]>d[cur]+arr[cur][j])
                {
                    d[j]=d[cur]+arr[cur][j];
                }
            }
        }
    }
}
void reset(){
    memset(d,0,sizeof(d));
    memset(visited,0,sizeof(visited));

}