Skip to content

Instantly share code, notes, and snippets.

@hhc0null
Created July 7, 2012 06:19
Show Gist options
  • Save hhc0null/3065044 to your computer and use it in GitHub Desktop.
Save hhc0null/3065044 to your computer and use it in GitHub Desktop.
aoj-0200-Traveling_Alone__One-way_Ticket_of_Youth-Runtime_Error.cpp
// HELP ME!!!!! WHAT'S WRONG!!!!
#include <iostream>
const unsigned int inf = 1 << 26;
const int MAX_OF_INFOMATIONS = 300;
const int MAX_OF_STATIONS = 100;
const int MAX_OF_ENQUIRIES = 200;
int dijk(int m, int n, int s, int g[2][MAX_OF_STATIONS][MAX_OF_STATIONS], int ary[2][MAX_OF_STATIONS][MAX_OF_STATIONS]) {
bool *used = new bool[n];
unsigned int *d = new unsigned int[n];
// std::cout << "n = " << n << " " << "s = " << s << std::endl;
for(int i = 0; i < n; i++)
d[i] = inf;
d[s] = 0;
for(int i = 0; i < n; i++)
used[i] = false;
while(true) {
int u = -1;
for(int v = 0; v < n; v++)
if(!used[v] && (u == -1 || d[v] < d[u]))
u = v;
// std::cout << "u = " << u << std::endl;
if(u == -1) break;
used[u] = true;
for(int v = 0; v < n; v++)
if(d[v] > d[u] + g[m][u][v])
d[v] = d[u] + g[m][u][v];
}
for(int i = 0; i < n; i++)
ary[m][s][i] = d[i];
// for(int i = 0; i < n; i++)
// std::cout << "d[" << i << "] = " << d[i] << std::endl;
return 0;
}
int main() {
int a[MAX_OF_INFOMATIONS] = {},
b[MAX_OF_INFOMATIONS] = {},
cost[MAX_OF_INFOMATIONS] = {},
time[MAX_OF_INFOMATIONS] = {},
p[MAX_OF_ENQUIRIES] = {},
q[MAX_OF_ENQUIRIES] = {},
r[MAX_OF_ENQUIRIES] = {},
d[2][MAX_OF_STATIONS][MAX_OF_STATIONS] = {},
g[2][MAX_OF_STATIONS][MAX_OF_STATIONS] = {};
int info, station, enquiry;
while(true) {
std::cin >> info >> station;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < station; j++) {
for(int k = 0; k < station; k++) {
g[i][j][k] = inf;
d[i][j][k] = inf;
}
}
}
if(!info && !station) break;
for(int i = 0; i < info; i++)
std::cin >> a[i] >> b[i] >> cost[i] >> time[i];
for(int i = 0; i < info; i++) {
a[i]--;
b[i]--;
}
for(int i = 0; i < info; i++) {
g[0][a[i]][b[i]] = time[i];
g[1][a[i]][b[i]] = cost[i];
g[0][b[i]][a[i]] = time[i];
g[1][b[i]][a[i]] = cost[i];
}
for(int i = 0; i < station; i++) {
dijk(0, station, i, g, d);
dijk(1, station, i, g, d);
}
std::cin >> enquiry;
for(int i = 0; i < enquiry; i++)
std::cin >> p[i] >> q[i] >> r[i];
for(int i = 0; i < enquiry; i++) {
p[i]--;
q[i]--;
}
for(int i = 0; i < enquiry; i++)
std::cout << d[!r[i]][p[i]][q[i]] << std::endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment