Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
2.3 kB
1
Indexable
Never
#define MAXA 63
#define INF 99999999
  
int PriceMap[MAXA][MAXA];
int TimeMap[MAXA][MAXA][24]; 
int dist[MAXA];
int visit[MAXA]; 
long long int visit_num = 0; 
int Num;
  
int dijk_find(int mS, int mE, int mTime, bool is_time) {
    visit_num++;
    for (register int i = 0; i < Num; i++) {
        dist[i] = INF;
    }
    dist[mS] = mTime;
    int min, v;
    int tmp;
  
    for (register int i = 0; i < Num; i++) {
        min = INF;
          
        for (register int j = 0; j < Num; j++) {
            if (visit[j] < visit_num && dist[j] < min) { 
                min = dist[j];
                v = j;
            }
        }
        if (v == mE)break;
        visit[v] = visit_num;
  
          
        for (register int j = 0; j < Num; j++) {
            if (is_time) { 
                tmp = min + TimeMap[v][j][min % 24];
                if (tmp < dist[j])
                    dist[j] = tmp;
            }
            else {
                tmp = min + PriceMap[v][j];
                if (tmp < dist[j])dist[j] = tmp;
            }
        }
  
    }
    return dist[mE] == INF ? -1 : dist[mE] - mTime;
  
}
  
void init(int N) {
    Num = N;
    for (register int i = 0; i < Num; i++) {
        for (register int j = 0; j < Num; j++) {
            PriceMap[i][j] = INF;
            for (register int k = 0; k < 24; k++) {
                TimeMap[i][j][k] = INF;
            }
        }
    }
}
  
void add(int mStartAirport, int mEndAirport, int mStartTime, int mTravelTime, int mPrice) {
    int check, dtime;
    if (mPrice < PriceMap[mStartAirport][mEndAirport])
        PriceMap[mStartAirport][mEndAirport] = mPrice;
    for (int i = 0; i < 24; i++) {
        check = i - mStartTime;
        dtime = mStartTime - i + mTravelTime;
        if (check > 0) {
            dtime = mStartTime + 24 - i + mTravelTime;
        }
        if (dtime < TimeMap[mStartAirport][mEndAirport][i]) {
            TimeMap[mStartAirport][mEndAirport][i] = dtime;
        }
    }
}
  
int minTravelTime(int mStartAirport, int mEndAirport, int mStartTime)
{
      
    return dijk_find(mStartAirport, mEndAirport, mStartTime, true);
}
  
int minPrice(int mStartAirport, int mEndAirport)
{
    return dijk_find(mStartAirport, mEndAirport, 0, false);
}