[editorial] ACM-ICPC 2008 Seoul Regional Problem C - Homing

  • VOCList
    VOCList

    문제 링크
    http://acm.kaist.ac.kr/2008/ProblemSet.pdf , C - Homing
    문제 설명
    어떤 사람이 출발지에서부터 목적지까지 자동차를 운전해서 가려고 합니다. 출발지와 목적지 사이에는 여러 도시들이 있고 서로 연결된 도시간의 거리 정보( = 그 길을 가는 데에 쓰이는 연료량)가 주어집니다. 이 사람은 출발지에서부터 목적지까지 가는 데에 필요한 최소한의 연료만을 넣어서 출발하고 싶습니다. 그러나 한 가지 문제가 있는데, 이 사람이 목적지를 향하던 도중에 기존에 존재하던 연결 중 최대 한 쌍 도시의 연결이 끊어질 수 있습니다. 그런데 이 사람은 그 연결이 끊어졌다는 것을 연결이 끊어진 끊어진 도시에 도착하였을 때 알 수 있습니다. 위와 같은 사실을 명심하며, 이 사람이 최소한 얼마나 많은 연료를 출발점에서 넣어야만 도착점에 무사히 도착할 수 있을까요? 도시의 숫자와 도시간 연결의 숫자는 모두 1이상 만 이하입니다. 모든 연결쌍이 무사할 경우의 최단거리 경로 역시 입력으로 주어집니다.
    문제 풀이
    [spoiler="더 보기..."]최대 한 쌍의 도로에 사고가 생길 수 있다는 사실에 주목해 보겠습니다.
    i) 만약 사고가 생긴 도로가 최단경로상에 있는 도로가 아니라면?
    이 때 여행자는 최단경로에서 필요한 연료만을 준비해서 가면 됩니다.
    ii) 만약 사고가 생긴 도로가 최단경로상에 있는 도로 중 하나라면?
    최단경로가 도시 s a b c d e t 를 순서대로 여행하는 것이라 가정하겠습니다. 만약에 b와 c를 연결하는 도로에 사고가 생겼다면, 여행자는 도시 b에 도착하였을 당시에 그 사실을 알 수 있습니다. 그럼 이 사실을 알아차린 시점에서 여행자가 도착지까지 가장 빠르게 갈 수 있는 방법은 b-c를 거치지 않으면서, b에서 가능한 가장 빠르게 t로 갈 수 있는 경로를 찾아보는 것입니다. 즉 이 문제는 b-c 의 거리가 무한대일 때 b에서 t까지의 최단경로를 찾는 것과 같습니다. 그 후에 s부터 b까지 가는 길에 걸리는 연료량을 더해준다면 b-c 도로에 사고가 생겼을 시 전체 여행에 필요한 최소의 연료량을 구할 수 있습니다. 위와 같은 방법을 s-a 도로에 사고가 생겼을 때, a-b 도로에 사고가 생겼을 때, ... e-t 도로에 사고가 생겼을 때를 각각 가정하여 최단거리를 계산해 보고, 그 최단거리중 가장 큰 값을 여행자가 필요한 최소의 연료량으로 생각하면 문제는 해결됩니다.
    사고가 생긴 도로의 인접도시에 도착하였을 때, 현재 도시에서 도착지까지의 최단 거리는 다익스트라를 통해서 구할 수 있습니다( O(VlgE) ). 이 다익스트라를 최단경로상에 있는 모든 도로의 갯수번 수행해야 함으로 다익스트라를 최대 (V-1)번 수행해야 합니다. 고로 본 풀이의 시간복잡도는 O(V^2lgE)입니다.
    사실 저는 대회 당시에 이 문제를 해결하지 못하였기 때문에 본 풀이가 실제 데이터에서 올바르게 작동할지 확신하지는 못합니다. 다만 YES를 받았던 팀 선수의 말에 따르면 이 풀이와 같은 시간복잡도로 실제 대회에서는 통과되었다고 합니다. 이 풀이 외에도 다른 풀이가 있다면 들어보고싶네요~[/spoiler]
    코드

    #include <cstdio>
    #include <vector>
    #include <queue>
    using namespace std;
    template <class T>
    class Dijkstra
    {
    public:
        enum { INF = 1000000002 };
        vector <vector <pair<T, int> > > eList;
        vector <bool> isVisit;
        Dijkstra(int n) { eList.resize(n); }
        void addEdge(T cost, int from, int to)
        {
            eList[from].push_back(make_pair(cost, to));
            return;
        }
        T editCost(T cost, int from, int to)
        {
            T ret=-1;
            int i;
            for(i=0;i<eList[from].size();i++)
            {
                if(eList[from][i].second==to) { ret=eList[from][i].first; break; }
            }
            eList[from][i].first=cost;
            return ret;
        }
        void getDist(int start, vector <T> &dist)
        {
            dist.clear();
            dist.resize(eList.size());
            isVisit.clear();
            isVisit.resize(eList.size());
            for(int i=0;i<eList.size();i++) dist[i]=INF;
            priority_queue <pair<T, int>, vector<pair<T, int> >, greater<pair<T, int> > > Q;
            Q.push(make_pair(0, start));
            for(int i=0;i<eList.size();i++)
            {
                while(!Q.empty() && isVisit[Q.top().second]) Q.pop();
                if(Q.empty()) break;
                pair<T, int> cur=Q.top();
                isVisit[cur.second]=true;
                dist[cur.second]=cur.first;
                int now=cur.second;
                T d=dist[cur.second];
                for(int j=0;j<eList[now].size();j++)
                    if(!isVisit[eList[now][j].second])
                        Q.push(make_pair(d+eList[now][j].first, eList[now][j].second));
                Q.pop();
            }
            return;
        }
    };
    int main(void)
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            int n, m;
            scanf("%d %d", &n, &m);
            Dijkstra <int> *graph = new Dijkstra <int>(n);
            for(int i=0;i<m;i++)
            {
                int temp[3];
                scanf("%d %d %d", temp, temp+1, temp+2);
                graph->addEdge(temp[2], temp[0], temp[1]);
                graph->addEdge(temp[2], temp[1], temp[0]);
            }
            int k, ans=-1;
            vector <int> dist, route;
            scanf("%d", &k);
            for(int i=0;i<k;i++) { int temp; scanf("%d", &temp); route.push_back(temp); }
            for(int i=1;i<k;i++)
            {
                int bef=graph->editCost(1000000002, route[i-1], route[i]);
                graph->editCost(1000000002, route[i], route[i-1]);
                graph->getDist(route[0], dist);
                int temp=dist[route[i-1]];
                graph->getDist(route[i-1], dist);
                temp+=dist[route[route.size()-1]];
                ans=max(ans, temp);
                graph->editCost(bef, route[i-1], route[i]);
                graph->editCost(bef, route[i], route[i-1]);
            }
            if(ans>=1000000002) printf("-1n");
            else printf("%dn", ans);
            delete graph;
        }
        return 0;
    }
    
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    12년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    테스트 우왕ㅋ굳ㅋ


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.