[그래프] DRUNKEN Drunken Driving

1. 문제

 

이 문제는 경유점이 중요하다.

 

한 정점마다 경유하는지를 조사하고 그 경유점으로 인해 최소거리가 되는지 조사하는

 

플로이드 알고리즘을 이용하여 이 문제를 해결할 수 있다.

 

2. 경유점 정렬

 

플로이드 알고리즘에서 정점들의 추가 순서는 알고리즘의 정당성에는 영향을 미치지 않는다.

 

따라서 delay에 대해 정렬하고, delay가 작은것 부터 조사하게 되면

 

경로에서 어떤점이 최대의 delay를 가지는지 별도의 연산이 필요없게된다. 

(항상 추가하는 정점이 현재 최대 delay이므로)

 

3. 플로이드 알고리즘: 잘못된 풀이

 

플로이드 알고리즘을 적용시킨 처음 풀이는 다음과 같았다.

 

정점 w를 추가 하였을 때

 

adj[i][w] + adj[w][j] + delay[w] 

 

에서 i->w 에서 생기는 딜레이와 w->j 에서 생기는 딜레이를 

 

빼주어 최소값을 구하였다.

 

하지만 이는 잘못된 풀이였다.

 

이는 adj[i][w] 와 adj[w][j]가 delay라는 추가 변수에 의해  '최단 경로'임을 보장하지 않기 때문이다.

 

void floyd()
{
    for(int i = 1; i < V+1; i++)
        adj[i][i] = 0;
    
    memset(W, 0, sizeof W);
    
 
 
    vector<pair<int, int> > order;
    for(int i = 1; i < V+1; ++i)
        order.push_back(make_pair(delay[i], i));
    sort(order.begin(), order.end());
    
 
    for(int i = 0; i < V; i++)
    {
        int k = order[i].second;
        for(int here = 1; here < V+1; here++)
                for(int there = 1; there < V+1; there++)
                {
                    int a = W[here][k];
                    int b = W[k][there];
                    int delayA = delay[a];
                    int delayB = delay[b];
                    int A = adj[here][k] - delayA;
                    int B = adj[k][there] - delayB;
 
                    if( adj[here][there] > A + B + delay[k])
                    {
          
                       W[here][there] = k;
                        adj[here][there] = A + B + delay[k];
                    }
                }
    }
}

 

4. 플로이드 알고리즘 : 두개의 행렬

 

책에서는 W라는 별도의 행렬을 만들어

 

딜레이를 적용시킨 거리와 적용시키지 않은 거리를

 

각각 구하여 딜레이를 더할 시 '최단 경로' 가 됨을 보장 시켰다.

 

 

점화식은 다음과 같다.

 

Ck(u, v) = min( Ds-[x](u,x) + Ds-[x](x, v)   ,   Ds-|x|(u, v) )

x ∈ S

 

 

W[u][v] = min( Cw(u, w) + Cw(w, v) + E[w] ) 

#include <algorithm>
#include <vector>
#include <iostream>
#include <utility>
#include <cstring>
 
using namespace std;
const int INF = 123456789;
int V, E;
int adj[500][500];
int delay[500];
int W[500][500];
 
void solve() {
    vector<pair<int, int> > order;
    for(int i = 0; i<V; ++i)
        order.push_back(make_pair(delay[i], i));
    sort(order.begin(), order.end());
    for(int i = 0; i < V; i++)
        for(int j = 0; j < V; j++)
            if(i==j)
                W[i][j] = 0;
            else
                W[i][j] = adj[i][j];
    for(int k = 0; k < V; k++)
    {
        int w = order[k].second;
        for(int i = 0; i < V; i++)
            for(int j = 0; j < V; j++)
            {
                adj[i][j] = min(adj[i][j], adj[i][w] + adj[w][j]);
                W[i][j] = min(adj[i][w] + delay[w] +adj[w][j], W[i][j]);
            }
    }
}
 
int main()
{
    int T;
    cin>>V>>E;
    delay[0] = 0;
    for(int i = 0; i < V; i++)
        for(int j = 0; j <V; j++)
            adj[i][j] = INF;
    for(int i = 0; i < V; i++)
        cin>>delay[i];
    for(int j = 0; j < E; j++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        adj[b-1][a-1] = c;
        adj[a-1][b-1] = c;
    }
    solve();
    
    cin>>T;
    while(T--)
    {
        int a, b;
        cin>>a>>b;
        cout<<W[a-1][b-1]<<"\n";
    }
}

 

DRUNKEN