(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](http://www.usaco.org/index.php?page=viewproblem2&cpid=210): 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](http://www.usaco.org/current/data/sol_mroute.html) 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.↵
↵
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](http://www.usaco.org/index.php?page=viewproblem2&cpid=210): 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](http://www.usaco.org/current/data/sol_mroute.html) 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.↵
