UVA762 We Ship Cheap

Graph, Dijkstra, Dijkstra 역추적

출처: UVA UVA762 We Ship Cheap


SOL)
다익스트라 문제로 정점이 JT, KV 대문자 알파뱃 2글자가 형태로 들어온다.
따라서 맵핑이 필요하다. 그리고 경로를 보여줘야 하기때문에 역추적을 해야한다.

예외처리) GG GG와 같이 같은 정점을 물어볼 경우.



[-] Collapse

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

map<string, int> mp;
vector<vector<pair<int, int> > > adj;
vector<int> path;
vector<int> dist;
string strStt, strFin;
int start, finish, edgeNum;;
string mapping[900];
int num; // 정점 수
void init(){
    mp.clear();
    path.clear();
    for (int i = 0; i < 900; i++)
        mapping[i] = "-1";
    adj.clear();
    adj = vector<vector<pair<int, int> > >(2*edgeNum+2);
}
void Dijkstra(int src){
    dist = vector<int>(num, 1234567890);
    path = vector<int>(num);
    priority_queue<pair<int, pair<int, int> > >pq;
    pq.push(make_pair(0, make_pair(src, src)));
    dist[src] = 0;
    int prev = src;
    while (!pq.empty()){
        int cost = -pq.top().first;
        int here = pq.top().second.first;
        int prev = pq.top().second.second;
        pq.pop();
        if (cost > dist[here]) continue;
        path[here] = prev;
        for (int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            int nextCost = cost + adj[here][i].second;
            if (nextCost < dist[there]){
                dist[there] = nextCost;
                pq.push(make_pair(-nextCost, make_pair(there, here)));
            }
        }
    }
}
void inSert(string str){
    if (mp.find(str) == mp.end()){
        mp.insert(pair<string, int>(str, num++));
        mapping[num - 1] = str;
    }
}
int main(){
    //freopen("input.txt", "r", stdin);
    string from, to;
    bool first = true;
    while (cin >> edgeNum){
        init();
        num = 0;
        if (!first) cout << endl;
        first = false;
        for (int i = 0; i < edgeNum; i++){
            cin >> from >> to;
            inSert(from);
            inSert(to);
            adj[mp[from]].push_back(make_pair(mp[to], 1));
            adj[mp[to]].push_back(make_pair(mp[from], 1));
        }
        cin >> strStt >> strFin;
        inSert(strStt);
        inSert(strFin);
        start = mp[strStt];
        finish = mp[strFin];
        if (edgeNum != 0)
            Dijkstra(start);
        if (edgeNum == 0 || dist[finish] == 1234567890) cout << "No route" << endl;
        else{
            vector<pair<string, string> > result;
            int right = mp[strFin];
            int left = path[right];
            if (right == left) continue;
            while (1){
                result.push_back(make_pair(mapping[left], mapping[right]));
                if (result[result.size() - 1].first == strStt)
                    break;
                right = left;
                left = path[right];
            }
            for (int i = result.size() - 1; i >= 0; i--){
                cout << result[i].first << " " << result[i].second << endl;
            }
        }

    }
}