12144 - Almost Shortest Path

All about problems in Volume 121. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
tahsynx
New poster
Posts: 1
Joined: Tue Dec 16, 2014 3:36 pm

Re: 12144 - Almost Shortest Path

Post by tahsynx » Tue Dec 16, 2014 3:42 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12144 - Almost Shortest Path

Post by brianfry713 » Wed Dec 24, 2014 3:38 am

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 121 (12100-12199)”