Ela and the Wiring Wizard (Codeforces 1737D)
Tags: Greedy, shortest paths

  Ela needs to send a large package from machine $$$1$$$ to machine $$$n$$$ through a network of machines. Currently, with the network condition, she complains that the network is too slow and the package can't arrive in time. Luckily, a Wiring Wizard offered her a helping hand.The network can be represented as an undirected connected graph with $$$n$$$ nodes, each node representing a machine. $$$m$$$ wires are used to connect them. Wire $$$i$$$ is used to connect machines $$$u_i$$$ and $$$v_i$$$, and has a weight $$$w_i$$$. The aforementioned large package, if going through wire $$$i$$$, will move from machine $$$u_i$$$ to machine $$$v_i$$$ (or vice versa) in exactly $$$w_i$$$ microseconds. The Wiring Wizard can use his spell an arbitrary number of times. For each spell, he will choose the wire of index $$$i$$$, connecting machine $$$u_i$$$ and $$$v_i$$$, and rewire it following these steps:  Choose one machine that is connected by this wire. Without loss of generality, let's choose $$$v_i$$$.  Choose a machine that is currently connecting to $$$v_i$$$ (including $$$u_i$$$), call it $$$t_i$$$. Disconnect the wire indexed $$$i$$$ from $$$v_i$$$, then using it to connect $$$u_i$$$ and $$$t_i$$$. The rewiring of wire $$$i$$$ will takes $$$w_i$$$ microseconds, and the weight of the wire will not change after this operation. After a rewiring, a machine might have some wire connect it with itself. Also, the Wiring Wizard has warned Ela that rewiring might cause temporary disconnections between some machines, but Ela just ignores it anyway. Her mission is to send the large package from machine $$$1$$$ to machine $$$n$$$ as fast as possible. Note that the Wizard can use his spell on a wire zero, one, or many times. To make sure the network works seamlessly while transferring the large package, once the package starts transferring from machine $$$1$$$, the Wiring Wizard cannot use his spell to move wires around anymore.Ela wonders, with the help of the Wiring Wizard, what is the least amount of time needed to transfer the large package from machine $$$1$$$ to $$$n$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.The first line contains $$$n$$$ and $$$m$$$ ($$$2 \le n \le 500$$$, $$$n - 1 \le m \le 250 000$$$), the number of nodes and number of wires, respectively.For the next $$$m$$$ lines, $$$i$$$-th line will contains $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^9$$$) - the indices 2 machines that are connected by the $$$i$$$-th edge and the weight of it.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$250 000$$$. The graph in each test case is guaranteed to be connected, no self-loops, but it can contain multiple edges.

Output: For each test case, output one integer denotes the least amount of time needed to transfer the large package from machine $$$1$$$ to $$$n$$$.

Note: Here is the graph in the first test case in the sample input:  Ela can ask the Wiring Wizard to use his spell on wire with the index of $$$7$$$, which is connecting machines $$$2$$$ and $$$3$$$. Then, since the machine $$$8$$$ is connected to machine $$$3$$$, the Wiring Wizard can disconnect wire $$$7$$$ from machine $$$3$$$ and connect it to machine $$$8$$$ in $$$3$$$ microseconds (weight of wire $$$3$$$).After that, the package can be sent from machine $$$1$$$ to machine $$$8$$$ in $$$6$$$ microseconds. Therefore, the answer is $$$3 + 6 = 9$$$ microseconds.Here is the graph in the third test case in the sample input:  

Sample Inputs:
3
8 9
1 2 3
6 4 5
3 5 6
6 1 3
7 4 4
3 8 4
2 3 3
7 8 5
4 5 2
4 5
1 2 1
2 4 1
3 4 1
3 1 1
1 3 2
8 8
4 6 92
7 1 65
6 5 43
6 7 96
4 3 74
4 8 54
7 4 99
2 5 22

Sample Outputs:
9
2
154

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    (n, m) = map(int, inp().split())
    g = [[] for i in range(n + 1)]
    e = [None] * m
    for i in range(m):
        (u, v, w) = map(int, inp().split())
        g[u].append((v, w))
        g[v].append((u, w))
        e[i] = (u, v, w)
    q = [1]
    qi = 0
    D = [-1] * (n + 1)
    D[1] = 0
    while qi < len(q):
        x = q[qi]
        qi += 1
        for (v, w) in g[x]:
            if D[v] < 0:
                D[v] = D[x] + 1
                q.append(v)
    q = [n]
    qi = 0
    E = [-1] * (n + 1)
    E[n] = 0
    while qi < len(q):
        x = q[qi]
        qi += 1
        for (v, w) in g[x]:
            if E[v] < 0:
                E[v] = E[x] + 1
                q.append(v)
    d = D[n]
    q = []
    F = [-1] * (n + 1)
    for i in range(1, n + 1):
        if D[i] + E[i] == d:
            q.append(i)
            F[i] = 1
    qi = 0
    while qi < len(q):
        x = q[qi]
        qi += 1
        for (v, w) in g[x]:
            if F[v] < 0:
                F[v] = F[x] + 1
                q.append(v)
    ans = 1e+18
    for (u, v, w) in e:
        ans = min(ans, w * (min(D[u] + E[v], D[v] + E[u], F[u] + d, F[v] + d) + 1))
    print(ans)

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import io
import os
import heapq
from collections import defaultdict, deque, Counter
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def solve():

    def bfs(start):
        nonlocal n
        q = deque([start])
        dis = [-1 for _ in range(n + 1)]
        dis[start] = 0
        while len(q) != 0:
            u = q.popleft()
            for v in graph[u]:
                if dis[v] == -1:
                    dis[v] = dis[u] + 1
                    q.append(v)
        return dis
    (n, m) = [int(word) for word in input().strip().split()]
    graph = [[] for _ in range(n + 1)]
    edges = []
    for _ in range(m):
        (u, v, w) = [int(word) for word in input().strip().split()]
        edges.append((u, v, w))
        graph[u].append(v)
        graph[v].append(u)
    d1 = bfs(1)
    d2 = bfs(n)
    ans = float('inf')
    dis = [0 for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i] = d1[i] + d2[i]
    vis = [False for _ in range(n + 1)]
    vis[0] = True
    for i in range(1, n + 1):
        mx = float('inf')
        u = -1
        for v in range(1, n + 1):
            if not vis[v] and dis[v] < mx:
                mx = dis[v]
                u = v
        for v in graph[u]:
            dis[v] = min(dis[v], dis[u] + 1)
        vis[u] = True
    for (u, v, w) in edges:
        d = min(d1[u] + d2[v], d1[v] + d2[u]) + 1
        d = min(d, min(dis[u], dis[v]) + 2)
        ans = min(ans, d * w)
    return ans

def main():
    t = int(input())
    for _ in range(t):
        print(solve())
if __name__ == '__main__':
    main()

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from functools import lru_cache
from itertools import accumulate
import math
import sys
from sys import stdout
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ii = lambda : int(input())
mii = lambda : map(int, input().split())
lmii = lambda : list(map(int, input().split()))
mod = 998244353
c2i = lambda c: ord(c) - ord('a')
i2c = lambda i: chr(ord('a') + i)

def solve():
    (n, m) = mii()
    edges = []
    for i in range(m):
        edges.append(lmii())
    disd = [0] * n
    d = [[] for _ in range(n)]
    for (x, y, w) in edges:
        d[x - 1].append(y - 1)
        d[y - 1].append(x - 1)

    def buildDis(u):
        stack = [u]
        dis = [0] * n
        while stack:
            temp = []
            while stack:
                p = stack.pop()
                for y in d[p]:
                    if y == u or dis[y] > 0:
                        continue
                    dis[y] = dis[p] + 1
                    temp.append(y)
            stack = temp
        return dis
    dis1 = buildDis(0)
    disn = buildDis(n - 1)
    d1n = dis1[n - 1]
    stack = []
    for i in range(n):
        if dis1[i] + disn[i] == d1n:
            stack.append(i)
            disd[i] = d1n
    while stack:
        temp = []
        while stack:
            p = stack.pop()
            for y in d[p]:
                if disd[y] > 0:
                    continue
                disd[y] = disd[p] + 1
                temp.append(y)
        stack = temp
    res = float('inf')
    for (x, y, w) in edges:
        x -= 1
        y -= 1
        u = min(dis1[x] + disn[y], disn[x] + dis1[y], 1 + disd[x], 1 + disd[y])
        res = min(res, (u + 1) * w)
    print(res)
for _ in range(ii()):
    solve()