32ος ΠΔΠ Γ' Φάση: Η τελευταία πίστα (supgame) - Λύση

Συγγραφέας: Βαγγέλης Κηπουρίδης

Ζητούμενο

Το πρόβλημά θυμίζει το γνωστό shortest path πρόβλημα: Δίνεται ένα κατευθυνόμενο γράφημα, και ζητείται η συντομότερη απόσταση από τον κόμβο \(s\) στον κόμβο \(t\). Η μόνη διαφορά είναι ότι υπάρχει ένας συγκεκριμένος κόμβος \(q\) τον οποίο δεν επιτρέπεται να επισκεφθούμε αν δεν έχουμε ήδη επισκεφθεί τον κόμβο \(p\). Για παράδειγμα, θεωρώντας ότι στο παρακάτω παράδειγμα όλες οι ακμές έχουν μήκος \(1\):

Αν \(p=2, q=7\), τότε μπορούμε να πάρουμε το συντομότερο μονοπάτι \(1-2-5-8\).
Αν \(p=7, q=2\), τότε βλέπουμε ότι πρέπει να περάσουμε από το \(7\) ώστε να μας επιτραπεί μετά να πάμε στο \(2\). Έτσι, η συντομότερη διαδρομή θα ήταν η \(1-7-1-2-5-8\). Προσέξτε ότι συνεπώς μπορεί να χρειαστεί να περάσουμε παραπάνω από μία φορά από κάποιους κόμβους (στο παράδειγμά μας από τον κόμβο \(1\)).
Αν \(p=7, q=5\), τότε θα προτιμούσαμε να πάρουμε το μονοπάτι \(1-2-3-4-8\).
Αν \(p=5, q=2\), τότε δεν υπάρχει τρόπος να φτάσουμε από το \(1\) στο \(8\).

Ειδική περίπτωση όπου δεν υπάρχει ζεύγος \((p,q)\) \((30\%)\)

Σε περίπτωση που δεν υπάρχει το ζεύγος \((p,q)\), το πρόβλημά μας είναι το γνωστό shortest path πρόβλημα. Το λύνουμε με τον αλγόριθμο Dijkstra. Σε περίπτωση που δεν έχετε ξανακούσει αυτό τον αλγόριθμο, δείτε εδώ για μία αρχική επεξήγηση, και κατόπιν εδώ για μια αποδοτικότερη υλοποίηση. Η πολυπλοκότητά του είναι \(\mathcal{O}(M\log{N})\), όπου \(M\) είναι το πλήθος ακμών στο γράφημα, και \(N\) το πλήθος κόμβων.

Ο κώδικας για το συγκεκριμένο υποπρόβλημα είναι ο παρακάτω, και ακολουθεί την αποδοτική υλοποίηση του Dijkstra.

#include <bits/stdc++.h>
using namespace std;
const long MAXN = 60000;
const long INF = 0x3f3f3f3f; //Huge number not overflowing, written in hexadecimal. Easy to remember.

long N, M, dDij[MAXN+2];
vector<long> e[MAXN+2], d[MAXN+2];
set< pair<long,long> > S;

void Dijkstra(long s) {
  for(long i=1; i<=N; ++i) dDij[i] = INF;
  dDij[s] = 0;
  S.insert( {0,s} );
  while (!S.empty()) {
    long curr = S.begin()->second;
    S.erase(S.begin());
    
    for(long i=0; i<e[curr].size(); ++i) {
      long neib = e[curr][i];
      if ( dDij[neib] > dDij[curr] + d[curr][i] ) {
        if ( dDij[neib] < INF ) {
          S.erase( S.find( {dDij[neib], neib} ) );
        }
        dDij[neib] = dDij[curr] + d[curr][i];
        S.insert( {dDij[neib], neib} );
      }
    }
  }
}

int main () {
  freopen("supgame.in","r",stdin);
  freopen("supgame.out","w",stdout);  
  long s, t, p, q;
  scanf("%ld %ld %ld %ld %ld %ld", &N, &M, &s, &t, &p, &q);
  for(long i=1; i<=M; ++i) {
    long a, b, c;
    scanf("%ld %ld %ld", &a, &b, &c);
    e[a].push_back(b);
    d[a].push_back(c);
  }
  Dijkstra(s);

  printf("%ld\n", dDij[t]);
}

Γενική περίπτωση

Η παρακάτω λύση έχει και πάλι πολυπλοκότητα \(\mathcal{O}(M\log{N})\), όπου \(M\) είναι το πλήθος ακμών στο γράφημα, και \(N\) το πλήθος κόμβων. Στηρίζεται σε μία απλή παρατήρηση:

Παρατήρηση: Μια διαδρομή από το \(s\) στο \(t\) μπορεί είτε να περνάει από τον κόμβο \(q\), είτε να μην περνάει. Αν βρούμε τη συντομότερη διαδρομή που περνάει από το \(q\), και τη συντομότερη διαδρομή που δεν περνάει από το \(q\), τότε η ελάχιστη των δύο είναι αυτή που ζητάμε. Θυμόμαστε ότι η συντομότερη διαδρομή που περνάει από το \(q\), πρέπει πρώτα να έχει περάσει ήδη από το \(p\).

Πώς υπολογίζουμε την ελάχιστη διαδρομή που δεν διέρχεται από το \(q\); Απλούστατα αφαιρούμε εντελώς το \(q\) από το γράφημά μας, και τρέχουμε τον αλγόριθμο Dijkstra.

Πώς υπολογίζουμε την ελάχιστη διαδρομή που διέρχεται από το \(q\); Για να διέρχεται από το \(q\), πρέπει πρώτα να έχει περάσει από το \(p\). Αυτό σημαίνει ότι η διαδρομή μας μπορεί να σπάσει σε \(3\) κομμάτια.

Τη διαδρομή από το \(s\) ως το \(p\) (χωρίς να επιτρέπεται να περάσουμε από το \(q\)).
Τη διαδρομή από το \(p\) ως το \(q\).
Τη διαδρομή από το \(q\) ως το \(t\).

Παρατηρούμε ότι για να είναι ελάχιστη η συνολική διαδρομή, αρκεί να είναι ελάχιστα και τα \(3\) κομμάτια που την απαρτίζουν. Επομένως, τρέχοντας \(3\) φορές τον αλγόριθμο Dijkstra, μπορούμε να βρούμε αυτά τα κομμάτια.

Παρακάτω αναφέρουμε δύο ακόμα ιδέες οι οποίες δεν είναι καθόλου απαραίτητες. Απλώς απλοποιούν τον κώδικά μας.

Σημείωση \(1\): Δεν αφαιρούμε πραγματικά το \(q\) από το γράφημα, όποτε αυτό χρειάζεται. Απλώς ενημερώνουμε τον Dijkstra, όποτε βλέπει το \(q\), να το αγνοεί.

Σημείωση \(2\): Προσέξτε ότι δε χρειάζεται να σπάσουμε τη διαδρομή σε \(3\) κομμάτια. Τα τελευταία δύο μπορούν να συνενωθούν, και να γίνει μία διαδρομή από το \(p\) ως το \(t\). Αυτό δε μας εγγυάται υποχρεωτικά ότι θα περάσουμε από το \(q\), αλλά αν έτσι δεν περνάμε από το \(q\) σημαίνει ότι ούτως ή άλλως η διαδρομή που δεν περνάει από το \(q\) είναι καλύτερη.

#include <bits/stdc++.h>
using namespace std;
const long MAXN = 60000;
const long INF = 0x3f3f3f3f; //Huge number not overflowing, written in hexadecimal. Easy to remember.

long N, M, dDij[MAXN+2];
vector<long> e[MAXN+2], d[MAXN+2];
set< pair<long,long> > S;

void Dijkstra(long s, long ignore) {
  for(long i=1; i<=N; ++i) dDij[i] = INF;
  dDij[s] = 0;
  S.insert( {0,s} );
  while (!S.empty()) {
    long curr = S.begin()->second;
    S.erase(S.begin());
    
    for(long i=0; i<e[curr].size(); ++i) {
      long neib = e[curr][i];
      if (neib==ignore) continue;
      if ( dDij[neib] > dDij[curr] + d[curr][i] ) {
        if ( dDij[neib] < INF ) {
          S.erase( S.find( {dDij[neib], neib} ) );
        }
        dDij[neib] = dDij[curr] + d[curr][i];
        S.insert( {dDij[neib], neib} );
      }
    }
  }
}

int main () {
  freopen("supgame.in","r",stdin);
  freopen("supgame.out","w",stdout);  
  long s, t, p, q, ans;
  scanf("%ld %ld %ld %ld %ld %ld", &N, &M, &s, &t, &p, &q);
  for(long i=1; i<=M; ++i) {
    long a, b, c;
    scanf("%ld %ld %ld", &a, &b, &c);
    e[a].push_back(b);
    d[a].push_back(c);
  }
  Dijkstra(s, q);
  ans = dDij[t];
  long tmp = dDij[p];
  Dijkstra(p, -1);
  ans = min(ans, tmp + dDij[t]);
  
  printf("%ld\n", ans);
}