Page 1 of 1

Re: 12144 - Almost Shortest Path

Posted: Tue Dec 16, 2014 3:42 pm
by tahsynx
my idea was :
1. find the sortest path
2. remove the routes for shortest path
3. while second shortest path = shortest path, remove the routes

why i'm getting WA :(

http://paste.ubuntu.com/9539956/

Code: Select all

#include <bits/stdc++.h>
using namespace std;

int n, parent[502], dis[502], graph[502][502];

struct data {
	int city, dist;
	bool operator < (const data &p) const {
		return dist > p.dist;
	}
};

void remove_path(int source, int destination)
{
	int m = source;
	parent[destination] = destination;

	while(m != destination) {
		graph[m][parent[m]] = 0;
		m = parent[m];
	}
}

int bfs(int source, int destination)
{
	for(int i = 0; i < n; i++) dis[i] = INT_MAX;
	dis[source] = 0;

	data u, v;
	u.city = source;
	u.dist = 0;
	
	priority_queue <data> q;
	q.push(u);

	while(!q.empty()) {
		u = q.top();
		q.pop();

		int ucost = dis[u.city];

		if(u.city == destination) return ucost;

		for(int i = 0; i < n; i++) {
			if(!graph[i][u.city]) continue;

			v.city = i;
			v.dist = ucost + graph[i][u.city];

			if(v.dist < dis[v.city]) {
				dis[v.city] = v.dist;
				parent[v.city] = u.city;
				q.push(v);
			}
		}
	}
	return dis[destination];
}

int main()
{
	int m, u, v, w, mn1, source, destination, mn2;

	while(scanf("%d%d", &n, &m)) {
		if(!n && !m) break;

		scanf("%d%d", &source, &destination);

		for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) graph[i][j] = 0;

		while(m--) {
			scanf("%d%d%d", &u, &v, &w);
			graph[u][v] = w;
		}

		mn1 = bfs(destination, source);

		if(mn1 == INT_MAX) {
			printf("-1\n");
			continue;
		}
		remove_path(source, destination);
		
		mn2 = bfs(destination, source);

		while(mn2 == mn1) {
			remove_path(source, destination);
			mn2 = bfs(destination, source);
		}
		if(mn2 == INT_MAX) printf("-1\n");
		else printf("%d\n", mn2);
	}



	return 0;
}

Re: 12144 - Almost Shortest Path

Posted: Wed Dec 24, 2014 3:38 am
by brianfry713
Try input:

Code: Select all

5 6
0 4
0 1 1
0 2 2
1 2 1
2 3 1
3 4 1
2 4 1
0 0
AC output -1
You need to solve this by running Dijkstra's algorithm up to two times. After the first run you must remove all edges that are part of any shortest path.