Untitled
unknown
plain_text
2 years ago
2.3 kB
12
Indexable
#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);
}Editor is loading...