Hey,
I am getting the correct answer for all the above given test cases except the one given below,
Code: Select all
1
30106 288 8942 9040
19264 22648 27446 23805 15890 6729 24370 15350 15006 31101 24393 3548 19629 12623 24084 19954 18756 11840 4966 7376 -1 -1
13931 26308 16944 32439 24626 11323 5537 21538 16118 2082 22929 16541 4833 31115 4639 29658 22704 9930 13977 2306 -1 -1
31673 22386 5021 28745 26924 19072 6270 5829 26777 15573 5097 16512 23986 13290 9161 18636 22355 24767 23655 15574 -1 -1
I get
122 for the above test case,
my code is attached below
I have made a directed graph from the given input and then I run dijkstra to get the answer. A particular subway station is connected to the next and previous stations in the same subway line via a 40km/hr fast subway line and to all other stations and the home and school via a 10km/hr walking line. The weight of the edges that I use is the time it takes to go from one vertex to another via walking or using a subway if possible. I cannot understand why this test case is giving the wrong answer while all the others give the correct answer
Code: Select all
#include <bits/stdc++.h>
#define INF 2000000000
#define VISITED 1
#define EXPLORED 0
#define UNVISITED -1
using namespace std;
vector<vector<pair<int,int> > >subway;
vector<vector<pair<int,double> > >adj;
map<pair<int,int>, int>vertex;
int V;
double eucDis(pair<int,int>a, pair<int,int>b) {
double x = a.first - b.first, y = a.second - b.second;
double ans = sqrt(x * x + y * y);
return ans;
}
void getAdj(void) {
adj.clear();
adj.resize(V);
adj[0].push_back(make_pair(1, eucDis(subway[0][0], subway[0][1])/10000*60));
adj[1].push_back(make_pair(0, eucDis(subway[0][0], subway[0][1])/10000*60));
int n = subway.size();
for (int i = 0; i < n; i++) {
int m = subway[i].size();
if (i != 0) {
for (int j = 1; j < m; j++) {
int u = vertex[make_pair(i, j)], v = vertex[make_pair(i, j - 1)];
adj[u].push_back(make_pair(v, eucDis(subway[i][j],subway[i][j - 1])/40000*60));
adj[v].push_back(make_pair(u, eucDis(subway[i][j],subway[i][j - 1])/40000*60));
}
}
for (int j = 0; j < m; j++) {
for (int a = 0; a < n; a++) {
if (a == i) {
continue;
}
int l = subway[a].size();
for (int b = 0; b < l; b++) {
int u = vertex[make_pair(i, j)], v = vertex[make_pair(a, b)];
adj[u].push_back(make_pair(v,eucDis(subway[i][j],subway[a][b])/10000*60));
}
}
}
}
}
double dijkstra(void) {
vector<double>dist(V, INF);
dist[0] = 0;
priority_queue<pair<int,double>,vector<pair<int,double> >,
greater<pair<int,double> > >pq;
pq.push(make_pair(0, 0));
while(!pq.empty()) {
pair<int,double>cur = pq.top();
pq.pop();
int u = cur.second, m = adj[u].size();
double du = cur.first;
if (dist[u] < du) {
continue;
}
for (int i = 0; i < m; i++) {
int v = adj[u][i].first;
double dv = adj[u][i].second;
if (dist[u] + dv < dist[v]) {
dist[v] = dist[u] + dv;
pq.push(make_pair(dist[v], v));
}
}
}
return dist[1];
}
int main(void) {
int test;
bool init = true;
cin >> test;
while (test > 0) {
test -= 1;
if (init == true) {
init = false;
} else {
cout << endl;
}
vector<pair<int,int> >points;
int x, y;
subway.clear();
vertex.clear();
V = 0;
for (int i = 0; i < 2; i++) {
cin >> x >> y;
points.push_back(make_pair(x, y));
}
subway.push_back(points);
string line;
getline(cin, line);
while (getline(cin, line), line != "") {
stringstream ss(line);
points.clear();
while (ss >> x >> y, x != -1 and y != -1) {
points.push_back(make_pair(x, y));
}
subway.push_back(points);
}
for (int i = 0; i < subway.size(); i++) {
for (int j = 0 ; j < subway[i].size(); j++) {
vertex[make_pair(i, j)] = V++;
}
}
getAdj();
double ans = dijkstra();
cout << round(ans) << endl;
}
return 0;
}
)
