Analysis: Dueling GPS's, by Allen Chen

This is a shortest path problem, where we have to find the minimum number of complaints that we recieve on the path. To do this we must build a new graph (call it G) where the edge lengths are either 0, 1, or 2, representing the number of complaints we get when we traverse an edge. Computing a shortest path from node 1 to node N in G then gives our answer.

To build the graph G, we consider each GPS separately, and we run Dijkstra's algorithm to calcutate the shortest path from node N to all other nodes after reversing all the edges on the graph (that is, we compute the shortest path from every node to node N in the original graph). Let dist[x] denote the shortet path distance from node x to node N. Then if dist[a] - dist[b] is equal to the actual edge length of edge (a,b), then edge (a,b) is on a shortest path to N, and our GPS will not complain on this edge. Otherwise, we add +1 to the length of (a,b) in G.

Below is my implementation. It uses Dijkstra that runs in O((N + M)logN) time for a total of three times, which is fast enough.

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<utility>
#include<cstring>
#include<stack>
#include<queue>

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> edge;

const int maxn = 10003, inf = 1 << 29;
int N, M;
vector<pii> va[maxn];
vector<pii> vb[maxn];
vector<pii> v[maxn];
int dist[3][maxn];

int dij(vector<pii> v[maxn], int a, int src) {
for (int i = 0; i < maxn; i++) {
dist[a][i] = inf;
}
dist[a][src] = 0;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push(pii(0, src));
while (pq.size()) {
int cur = pq.top().second;
int dst = pq.top().first;
pq.pop();
if (dst != dist[a][cur]) {
continue;
}
for (int i = 0; i < v[cur].size(); i++) {
int nxt = v[cur][i].first;
int c = v[cur][i].second + dist[a][cur];
if (c < dist[a][nxt]) {
dist[a][nxt] = c;
pq.push(pii(dist[a][nxt], nxt));
}
}
}
return dist[a][N - 1];
}
int main() {
freopen("gpsduel.in","r",stdin);
freopen("gpsduel.out","w",stdout);
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++) {
int a, b, p, q;
scanf("%d%d%d%d", &a, &b, &p, &q);
a--; b--;
va[b].push_back(pii(a, p));
vb[b].push_back(pii(a, q));
}
dij(va, 0, N - 1);
dij(vb, 1, N - 1);

for (int cur = 0; cur < N; cur++) {
for (int j = 0; j < va[cur].size(); j++) {
int nxt = va[cur][j].first;
int c = 0;
int dst1 = va[cur][j].second, dst2 = vb[cur][j].second;
if (dist[0][nxt] - dist[0][cur] != dst1) c++;
if (dist[1][nxt] - dist[1][cur] != dst2) c++;
v[nxt].push_back(pii(cur, c));
}
}

int ans = dij(v, 2, 0);
printf("%d\n", ans);
}
```