UVA117 The Postal Worker Rings Once

Graph, Dijsktra, Euler

출처: UVA UVA117 The Postal Worker Rings Once


SOL)
오일러 회로가있는지 검사 후 있다면 주어진 도로의 합을 출력
만약 회로는 없지만 경로가 있는 경우면 두 홀수 디그리를 갖는
정점의 최단거리 경로를 주어진 도로의 총합과 더해주면 된다.
이 때 Dijkstra를 이용한다.


[-] Collapse

#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;

vector<vector<pair<int, int> > >adj;
int result;
int start, finish;
int n;
void init(){
    adj = vector<vector<pair<int, int> > >('z' - 'a' + 1);
    n = result = 0;
}
bool ok(){
    bool first = true;
    for (int i = 0; i < adj.size(); i++){
        if (adj[i].size() % 2 == 1){
            if (first)
                start = i;
            else {
                finish = i;
                return false;
            }
            first = false;
        }
    }
    return true;
}
vector<int> Dijkstra(int src){
    vector<int> dist('z' - 'a' + 2, 1234567890);
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0, src));
    while (!pq.empty()){
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if (dist[here] < cost) continue;
        for (int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            int nextDist = cost + adj[here][i].second;
            if (dist[there] > nextDist) {
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
            }
        }
    }
    return dist;
}

int main(){
    //freopen("input.txt", "r", stdin);
    string str;
    while (cin >> str){
        init();
        while (true){
            adj[str[0] - 'a'].push_back(make_pair(str[str.size() - 1] - 'a', str.size()));
            adj[str[str.size() - 1] - 'a'].push_back(make_pair(str[0] - 'a', str.size()));
            result += str.size();
            n++;
            cin >> str;
            if (str == "deadend") break;
        }
        if (ok())
            cout << result << endl;
        else{
            vector<int> dist = Dijkstra(start);
            cout << result + dist[finish] << endl;
        }

    }
}