Editorial for Mostly Talking


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

This problem is asking for the shortest distance from node 1 to node N given that you can use 1 extra edge from a pile. The naive solution would be to keep a running best and iterate through each edge, add it to the graph, run a shortest path algorithm (Dijkstra's or SPFA?), and then delete it from the graph. Unfortunately, this would not get you all the test cases as it is too slow.

The intended solution was to run Dijkstra's once from node 1, then reverse the graph and run Dijkstra's again from node N. After, keep a running best and for each edge,

best = min(best, forw[startingnode] + weightofedge + back[endingnode])

where forw is the array holding minimum distance from node 1, back is the array holding minimum distances from node N, startingnode is the first endpoint of the edge, endingnode is the second endpoint of the edge, and weightofedge is its weight.

Why does this work? Well, for an edge to make any difference, it must be a part of the shortest path when we add it to the graph. How do we compute the shortest path including an edge e? Well, any path containing edge e can be split into three parts: The path from 1 to the start of e, the weight of e itself, and the path from the end of e to N. To minimize the total distance of this path, we just need to ensure the first and third parts are minimized! Since for any edge, the first part will start from node 1, we just need one run of Dijkstra's or SPFA starting at node 1 to answer all queries. Since for any edge, the third part will end on node N, we just need one more run of Dijkstra's starting from node N to answer all the queries (to do this, we need to reverse the edges)! Below is the official solution, in C++ 11.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 500001, inf = 999999999;

struct edge {
    int from, to , weight;
};
vector<edge> graph[maxn],revgraph[maxn],cindy;
int n,m,d,a,b,g,k,forw[maxn],rev[maxn], ans = inf;
bool flag[maxn];
queue <int> q;

void spfa(int start) {
    forw[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        flag[u] = false;
        for (int i = 0;i<graph[u].size();i++) {
            int dest = graph[u][i].to;
            int cost = graph[u][i].weight;
            if (forw[dest] > forw[u] + cost) {
                forw[dest] = forw[u] + cost;
                if (!flag[dest]) {
                    q.push(dest);
                    flag[dest] = true;
                }
            }
        }
    }
}

void spfarev(int start) {
    rev[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        flag[u] = false;
        for (int i = 0;i<revgraph[u].size();i++) {
            int dest = revgraph[u][i].to;
            int cost = revgraph[u][i].weight;
            if (rev[dest] > rev[u] + cost) {
                rev[dest] = rev[u] + cost;
                if (!flag[dest]) {
                    q.push(dest);
                    flag[dest] = true;
                }
            }
        }
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for (int i = 0 ;i<m;i++) {
        scanf("%d%d%d",&a,&b,&k);
        graph[a].push_back((edge){a,b,k});
        revgraph[b].push_back((edge){b,a,k});
    }
    scanf("%d",&d);
    for (int i = 0;i<d;i++) {
        scanf("%d%d%d",&a,&b,&g);
        cindy.push_back((edge){a,b,g});
    }

    for (int i = 1; i<=n;i++) { // initialize dp arrays
        forw[i] = inf;
        rev[i] = inf;
    }

    spfa(1);            // spfa forwards
    for (int i = 1;i<=n;i++) // reset the flag for reuse
        flag[i] = false;
    spfarev(n);             // spfa backwards

    ans = forw[n];
    for (int i = 0;i<cindy.size();i++) { // loop through edges for answer
        int to = cindy[i].to; int from = cindy[i].from; int weight = cindy[i].weight;
        int curr = forw[from] + rev[to] + weight;
        ans = min(ans,curr);
    }
    if (ans == inf) puts("-1\n");
    else printf("%d\n",ans);
}

Comments

There are no comments at the moment.