Does Dijkstra work on graphs with distances that depend on 2 variables?

Правка en2, от Iwaskid, 2017-01-06 23:40:24

(First time writing a blog, sorry for any confusions)

Normally, in a shortest-path problem, the distance from one node to another node usually is determined by only one variable (usually the "cost" of that edge), which can be implemented by maintaining a priority queue of nodes based on the values of the edges.

Recently I encountered a USACO Problem (link here: where the cost between an edge depend on two variables: the latency of the pipes, and the minimum capacity of the pipes. While the problem solution provided by USACO tells us to consider latency and capacity separately (by iterating over all possible capacities and run Dijkstra on edges that have at least that capacity), I wonder if it is possible to use just one Dijkstra search, while considering both variables at the same time. Here is my code:

#include<iostream>
#include<fstream>
#include<queue>
#include<math.h>
#include<functional>
#include<algorithm>
#include<vector>
using namespace std;
#define mp make_pair
#define MAX 1e9
int n, m, x;
class sss {
public:
	double lat, cap;
	sss(double n1, double n2) {
		lat = n1, cap = n2;
	}
	double calct() {
		return lat + x / cap;
	}
};
class cmpsss {
public:
	bool operator()(pair<sss,int>c1, pair<sss,int>c2) {
		return c1.first.calct() > c2.first.calct();
	}
};
vector<pair<int,pair<int, int>>>neibs[501];

double dist[501];
void dijk() {
	for (int i = 0; i <= n; i++) {
		dist[i] = MAX;
	}
	dist[1] = 0;
	priority_queue<pair<sss, int>, vector<pair<sss, int>>, cmpsss> q;
	q.push(mp(sss(0, MAX), 1));
	while (!q.empty()) {
		pair<sss, int> nownode = q.top(); q.pop();
		int cur = nownode.second;
		double curlat = nownode.first.lat;
		double curcap = nownode.first.cap;
		if (dist[cur] < nownode.first.calct()&&cur!=1)continue;
		for (int i = 0; i < neibs[cur].size(); i++) {
			int next = neibs[cur][i].first;
			double nextlat = neibs[cur][i].second.first;
			double nextcap = min(int(curcap), neibs[cur][i].second.second);
			if (dist[next] > curlat + nextlat + x / nextcap) {
				dist[next] = curlat + nextlat + x / nextcap;
				q.push(mp(sss(nextlat, nextcap), next));
			}
		}
	}
}
int main() {
	ifstream fin("mroute.in");
	ofstream fout("mroute.out");
	fin >> n >> m >> x;
	for (int i = 0; i < m; i++) {
		int node1, node2, cost, cap;
		fin >> node1 >> node2 >> cost >> cap;
		neibs[node1].push_back(mp(node2, mp(cost,cap)));
		neibs[node2].push_back(mp(node1, mp(cost,cap)));
	
	}
	dijk();
	fout << floor(dist[n]) << endl;
	return 0;

}

In my code, I wrote a class called sss to store both the latency and the capacity. The member function calct() calculates the combined cost of both variables, given the edge. The priority queue compares two nodes using the same function calct(). However, this did not work when I submitted it online. Is my solution wrong, or Dijkstra just does not work when the cost is determined by two variables? Thanks.

Теги dijkstra, dijkstras validity, shortest path, graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Iwaskid 2017-01-06 23:40:24 1
en1 Английский Iwaskid 2017-01-06 23:38:45 3174 Initial revision (published)