I’ve made two copies of the input graph and connected these two copies with each of the k bidirectional edges: - (u, v) such that u of the first copy is connected to v of the second copy and v of the first copy is connected to u of the second copy. I’ve then run Dijkstra’s Algorithm once on this new graph and the printed the required answer. I think my solution and code should be correct and I can’t figure out the reason behind the WA. I’ll post my code below and hope someone can provide a testcase for which my code gives the wrong answer:
#include<iostream>
#include<vector>
#define INF 1000000001
#define pii pair<int, int>
using namespace std;
void heapify_down(vector<pii> &heap, int idx, int* inx)
{
while(2*idx+1 < heap.size() && (heap[idx].second > heap[2*idx+1].second || ((2*idx+2 >= heap.size()) ? false : heap[idx].second > heap[2*idx+2].second)))
{
int x = (2*idx + 2 < heap.size() && heap[2*idx+1].second > heap[2*idx+2].second) ? 2*idx+2: 2*idx+1;
pii t = heap[idx], td = heap[x];
swap(heap[idx], heap[x]);
inx[t.first] = x;
inx[td.first] = idx;
idx = x;
}
}
void heapify_up(vector<pii> &heap, int idx, int* inx)
{
int y;
while(idx && heap[idx].second < heap[y=idx/2 - ((idx%2)?0:1)].second)
{
pii t = heap[idx], td = heap[y];
swap(heap[idx], heap[y]);
inx[t.first] = y;
inx[td.first] = idx;
idx = y;
}
}
void ins_heap(vector<pii> &heap, pii node, int* inx)
{
heap.push_back(node);
inx[node.first] = heap.size()-1;
heapify_up(heap, inx[node.first], inx);
}
void extr_heap(vector<pii> &heap, int* inx)
{
heap[0] = heap.back();
inx[heap[heap.size()-1].first] = 0;
heap.pop_back();
heapify_down(heap, 0, inx);
}
void change_key(vector<pii> &heap, int idx, int val, int* inx)
{
heap[idx].second = val;
heapify_up(heap, idx, inx);
heapify_down(heap, idx, inx);
}
pii get_min(vector<pii> &heap)
{
return heap[0];
}
int main()
{
int Q;
cin >> Q;
while(Q--)
{
int N, M, K, S, T;
cin >> N >> M >> K >> S >> T;
vector<vector <pii> > graph(2*N+2);
for(int i = 0; i < M; i++)
{
int u, v, l;
cin >> u >> v >> l;;
graph[u].push_back(make_pair(v, l));
graph[N+u].push_back(make_pair(N+v, l));
}
graph[0].push_back(make_pair(S, 0));
graph[0].push_back(make_pair(S+N, 0));
graph[T].push_back(make_pair(2*N+1, 0));
graph[T+N].push_back(make_pair(2*N+1, 0));
for(int i = 1; i <= K; i++)
{
int u, v, l;
cin >> u >> v >> l;
graph[u].push_back(make_pair(v+N, l));
graph[v].push_back(make_pair(u+N, l));
}
vector<pii> heap;
int inx[2*N+2];
bool visited[2*N+2];
for(int i = 0; i < 2*N+2; i++)
{
heap.push_back(make_pair(i, ((i)?INF:0)));
inx[i] = i;
visited[i] = false;
}
while(!heap.empty())
{
pii t = get_min(heap);
extr_heap(heap, inx);
visited[t.first] = true;
if(t.first == 2*N+1)cout << ((t.second < INF)?t.second:-1) << endl;
for(int i = 0; i < graph[t.first].size(); i++)
{
if(!visited[graph[t.first][i].first])
{
if(heap[inx[graph[t.first][i].first]].second > t.second+graph[t.first][i].second)change_key(heap, inx[graph[t.first][i].first], t.second+graph[t.first][i].second, inx);
}
}
}
}
return 0;
}
Thank you.