Untitled
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); }