Advertisement
mickypinata

USACO-T038: Bessie Come Home

Dec 16th, 2021
845
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: comehome
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define f first
  11. #define s second
  12. typedef pair<char, int> pci;
  13. typedef pair<int, char> pic;
  14.  
  15. vector<pci> adj[2][26];
  16. int dist[2][26];
  17. bool visited[2][26];
  18.  
  19. vector<pci> &adjAcc(char c){
  20.     if(isupper(c)){
  21.         return adj[0][c - 'A'];
  22.     } else {
  23.         return adj[1][c - 'a'];
  24.     }
  25. }
  26.  
  27. int &distAcc(char c){
  28.     if(isupper(c)){
  29.         return dist[0][c - 'A'];
  30.     } else {
  31.         return dist[1][c - 'a'];
  32.     }
  33. }
  34.  
  35. bool &visitedAcc(char c){
  36.     if(isupper(c)){
  37.         return visited[0][c - 'A'];
  38.     } else {
  39.         return visited[1][c - 'a'];
  40.     }
  41. }
  42.  
  43. int main(){
  44.     freopen("comehome.in", "r", stdin);
  45.     freopen("comehome.out", "w", stdout);
  46.  
  47.     int nEdge;
  48.     scanf("%d", &nEdge);
  49.     for(int i = 1; i <= nEdge; ++i){
  50.         char u, v;
  51.         int w;
  52.         scanf(" %c %c%d", &u, &v, &w);
  53.         adjAcc(u).emplace_back(v, w);
  54.         adjAcc(v).emplace_back(u, w);
  55.     }
  56.     for(int i = 0; i < 26; ++i){
  57.         dist[0][i] = 1e9;
  58.         dist[1][i] = 1e9;
  59.     }
  60.     priority_queue<pic, vector<pic>, greater<pic>> pq;
  61.     distAcc('Z') = 0;
  62.     pq.emplace(distAcc('Z'), 'Z');
  63.     while(!pq.empty()){
  64.         char u = pq.top().s;
  65.         pq.pop();
  66.         if(isupper(u) && u != 'Z'){
  67.             cout << u << ' ' << distAcc(u) << '\n';
  68.             fclose(stdin);
  69.             fclose(stdout);
  70.             return 0;
  71.         }
  72.         if(visitedAcc(u)){
  73.             continue;
  74.         }
  75.         visitedAcc(u) = true;
  76.         for(pci nxt : adjAcc(u)){
  77.             char v = nxt.f;
  78.             int w = nxt.s;
  79.             if(!visitedAcc(v) && distAcc(u) + w < distAcc(v)){
  80.                 distAcc(v) = distAcc(u) + w;
  81.                 pq.emplace(distAcc(v), v);
  82.             }
  83.         }
  84.     }
  85.  
  86.     fclose(stdin);
  87.     fclose(stdout);
  88.     return 0;
  89. }
  90.  
Advertisement
RAW Paste Data Copied
Advertisement