Xin chào mọi người, đây là đề bài:
Đây là ví dụ:
Ý tưởng là khi tìm đường từ S->T, thì mình dùng Dijkstra cho đỉnh S tương ứng với đồ thị G và đỉnh T tương ứng với đồ thị Reverse của G, cho đến khi gặp nhau tại điểm T, thì nó sẽ có 2 trường hợp xảy ra:
1 là đường đi ngắn nhất sẽ đi qua T(result1), 1 là đường đi ngắn nhất sẽ không đi qua T. Nếu nó không đi qua T thì lui lại 1 node rồi tính tổng quảng đường (result2) rồi so sánh result1 và result2.(cái này em tự đoán dựa vào hình bên dưới:)
Em xin giải thích 1 ít: Tất cả dữ liệu đầu vào đều -1 để tiện lưu trữ trong vector, adj_ là vector lưu các đỉnh, cost_ là vector lưu các trọng số tương ứng với các đỉnh, q là vector lưu 2 cái min priority queue, tương tự với các vector distance_, visited, parent (0 là của đồ thị G, 1 là của Reverse Graph của G). Và đây là code của em. Code của em bị sai gì đó mà em không biết, mong các anh chị xem và gợi ý giúp em, em xin cảm ơn mọi người.
#include "pch.h"
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <queue>
#include <limits>
#include <utility>
using namespace std;
// External vector of size 2 - for forward and backward search.
// Internal 2-dimensional vector is vector of adjacency lists for each node.
typedef vector<vector<vector<int>>> Adj;
// Distances can grow out of int type
typedef long long Len;
// Vector of two priority queues - for forward and backward searches.
// Each priority queue stores the closest unprocessed node in its head.
typedef vector<priority_queue<pair<Len, int>, vector<pair<Len, int>>, greater<pair<Len, int>>>> Queue;
const Len infinite = numeric_limits<Len>::max() / 4;
class Bidijkstra {
// Number of nodes
int n_;
// Graph adj_[0] and cost_[0] correspond to the initial graph,
// adj_[1] and cost_[1] correspond to the reversed graph.
// Graphs are stored as vectors of adjacency lists corresponding
// to nodes.
// Adjacency list itself is stored in adj_, and the corresponding
// edge costs are stored in cost_.
Adj adj_;
Adj cost_;
public:
Bidijkstra(int n, Adj adj, Adj cost)
: n_(n), adj_(adj), cost_(cost)
{
}
// Processes visit of either forward or backward search
// (determined by value of side), to node v trying to
// relax the current distance by dist
void updateQueue(Queue&q)
{
for (int i = 0; i < adj_[0].size(); i++)
{
q[0].push(make_pair(infinite, i));
q[1].push(make_pair(infinite, i));
}
}
// turn distance of vertex v into dist
void visit(Queue& q, int side, int v, Len dist) {
// Implement this method yourself
queue<pair<Len, int>> tempQueue;
while (!q[side].empty())
{
pair<Len, int> current = q[side].top();
q[side].pop();
if (current.second == v)
{
current.first = dist;
tempQueue.push(current);
break;
}
tempQueue.push(current);
}
while (!tempQueue.empty())
{
q[side].push(tempQueue.front());
tempQueue.pop();
}
}
// Returns the distance from s to t in the graph.
Len query(int s, int t) {
if (s == t) return 0;
Queue q(2);
// add all vertex with infinity distance into 2 queue
updateQueue(q);
visit(q, 0, s, 0);
visit(q, 1, t, 0);
// Implement the rest of the algorithm yourself
Len result1 = infinite, result2 = infinite;
vector<vector<Len>> distance_(2, vector<Len>(adj_[0].size(), infinite));
vector<vector<bool>> visited(2, vector<bool>(adj_[0].size(), false));
vector<vector<int>> parent(2, vector<int>(adj_[0].size(), -1));
distance_[0][s] = 0;
distance_[1][t] = 0;
int u, v;
while (!q[0].empty() && !q[1].empty())
{
pair<Len, int> currentFor = q[0].top();
q[0].pop();
visited[0][currentFor.second] = true;
for (int i = 0; i < adj_[0][currentFor.second].size(); i++)
{
int neighbour = adj_[0][currentFor.second][i];
if (visited[0][neighbour] == true)
continue;
Len dist = distance_[0][currentFor.second] + cost_[0][currentFor.second][i];
if (distance_[0][neighbour] > dist)
{
distance_[0][neighbour] = dist;
visit(q, 0, neighbour, dist);
parent[0][neighbour] = currentFor.second;
}
}
pair<Len, int> currentBack = q[1].top();
q[1].pop();
if (visited[1][currentBack.second] == false && visited[0][currentBack.second] == false)
{
visited[1][currentBack.second] == true;
for (int i = 0; i < adj_[1][currentBack.second].size(); i++)
{
int neighbour = adj_[1][currentBack.second][i];
if (visited[1][neighbour] == true)
continue;
Len dist = distance_[1][currentBack.second] + cost_[1][currentBack.second][i];
if (distance_[1][neighbour] > dist)
{
distance_[1][neighbour] = dist;
visit(q, 1, neighbour, dist);
parent[1][neighbour] = currentBack.second;
}
}
}
else
{
// found the middle vertex
result1 = distance_[0][currentFor.second] + distance_[1][currentBack.second];
u = parent[0][currentFor.second];
v = parent[1][currentBack.second];
}
if (result1 < infinite) break;
}
if (v == -1 || u == -1) return -1;
for (int i = 0; i < adj_[0][u].size(); i++)
{
int neighbour = adj_[0][u][i];
if (v == neighbour)
{
result2 = distance_[0][u] + distance_[1][v] + cost_[0][u][i];
break;
}
}
return min(result1, result2);
}
};
int main() {
int n, m;
cin >> n >> m;
Adj adj(2, vector<vector<int>>(n));
Adj cost(2, vector<vector<int>>(n));
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
adj[0][u - 1].push_back(v - 1);
cost[0][u - 1].push_back(c);
adj[1][v - 1].push_back(u - 1);
cost[1][v - 1].push_back(c);
}
Bidijkstra bidij(n, adj, cost);
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
int u, v;
cin >> u >> v;
cout << bidij.query(u - 1, v - 1) << endl;
}
}
Đây là test case mà em past được:
5 20
1 2 667
1 3 677
1 4 700
1 5 622
2 1 118
2 3 325
2 4 784
2 5 11
3 1 585
3 2 956
3 4 551
3 5 559
4 1 503
4 2 722
4 3 331
4 5 366
5 1 880
5 2 883
5 3 461
5 4 228
10
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
Output:
0
667
677
700
622
118
0
325
239
11
Còn đây là một trong các test case cuối cùng của bài toán:
https://www.cc.gatech.edu/dimacs10/archive/clustering.shtml
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?