Special Shortest Walk - Codechef.cpp

#include<bits/stdc++.h>
#define maxn 100005

using namespace std;

const long long int inf = 1LL << 60;
long long int c_decrement[maxn], c_increment[maxn], dist[maxn];
vector<pair<long long int, long long int>> decrement[maxn], increment[maxn];

void dijkstra() {
    priority_queue<pair<pair<long long int, long long int>, pair<long long int, long long int>>> q;
    long long int x, y, wt, key, j, v;
    int source, dest, n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        decrement[i].clear();
        increment[i].clear();
        c_decrement[i] = 0;
        c_increment[i] = 0;
        dist[i] = inf;
    }
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> wt;
        decrement[x].push_back(make_pair(-wt, y));
        decrement[y].push_back(make_pair(-wt, x));
        increment[x].push_back(make_pair(wt, y));
        increment[y].push_back(make_pair(wt, x));
    }
    cin >> source >> dest;
    for (int i = 1; i <= n; ++i) {
        sort(decrement[i].begin(), decrement[i].end());
        sort(increment[i].begin(), increment[i].end());
    }
    q.push(make_pair(make_pair(0, 0), make_pair(0, source)));
    while (!q.empty()) {
        auto front = q.top();
        q.pop();
        v = front.second.second;
        wt = front.second.first;
        key = -front.first.first;
        dist[v] = min(key, dist[v]);
        if (front.first.second & 1) {
            for (j = c_increment[v]; j < increment[v].size(); j++) {
                if (wt > increment[v][j].first)
                    q.push(make_pair(make_pair(-(key + increment[v][j].first), 0),
                                     make_pair(increment[v][j].first, increment[v][j].second)));
                else
                    break;
            }
            c_increment[v] = j;
        } else {
            for (j = c_decrement[v]; j < decrement[v].size(); j++) {
                if (wt < -(decrement[v][j].first))
                    q.push(make_pair(make_pair(-(key - decrement[v][j].first), 1),
                                     make_pair(-decrement[v][j].first, decrement[v][j].second)));
                else
                    break;
            }
            c_decrement[v] = j;
        }
        if (dist[dest] != inf)
            break;
    }
    if (dist[dest] != inf)
        cout << dist[dest] << '\n';
    else
        cout << "No Solution\n";
}

int main() {
    int t;
    cin >> t;
    while (t--)
        dijkstra();
    return 0;
}