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