Given an undirected connected graph of n vertices and list of m edges in a graph and for each pair of vertices that are connected by an edge. 
There are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. 
You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge. Your task is to find the shortest path from a to b satisfying the above condition. If there is no path from a to b, return -1.
 
Example 1:
Input:
n = 4, m = 4
a = 2, b = 4
edges = {{1, 2, 1, 4}, {1, 3, 2, 4},
         {1, 4, 3, 1}, {2, 4, 6, 5}}
Output:
2
Explanation:
We can follow the path 2 -> 1 -> 4.
This gives a distance of 1+3 = 4 if we follow
all straight paths. But we can take the curved
path  from 1 -> 4, which costs 1. This
will result in a cost of 1+1 = 2
Example 2:
Input:
n = 2, m = 1
a = 1, b = 2
edges = {{1, 2, 4, 1}}
Output :
1
Explanation:
Take the curved path from 1 to 2 which costs 1. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function shortestPath() which takes 4 integers n, m, a, and b, and a list of lists named edges of size m as input and returns the cost of shortest path from a to b.
Expected Time Complexity: O((m+n)log(n))
Expected Auxiliary Space: O(n+m)
Constraints:
1 ≤ n,m ≤ 10^{5}
1 ≤ a,b ≤ n
weight of edges ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Shortest paths

Starter code: #User function Template for python3



class Solution:

    def shortestPath(self, n, m, a, b, edges):

        # code here 

Solutions:
class Solution:

	def shortestPath(self, n, m, a, b, edges):
		from collections import defaultdict
		g = defaultdict(list)
		for (x, y, w1, w2) in edges:
			g[x].append((y, w1, w2))
			g[y].append((x, w1, w2))
		costs = {(a, -1): 0}
		q = [(0, -1, a)]
		while q:
			(cost, k, node) = heappop(q)
			if node == b:
				return cost
			for (nbr, w1, w2) in g[node]:
				scost = cost + w1
				ccost = cost + w2
				if k == 0:
					if (nbr, 0) in costs and costs[nbr, 0] < scost:
						continue
					if (nbr, -1) in costs and costs[nbr, -1] <= scost:
						continue
					costs[nbr, 0] = scost
					heappush(q, (scost, 0, nbr))
				else:
					if (nbr, -1) not in costs or costs[nbr, -1] > scost:
						costs[nbr, -1] = scost
						heappush(q, (scost, -1, nbr))
					if (nbr, 0) not in costs or costs[nbr, 0] > ccost:
						if (nbr, -1) not in costs or costs[nbr, -1] > ccost:
							costs[nbr, 0] = ccost
							heappush(q, (ccost, 0, nbr))
		return -1


class Solution:

	def dijkstra(self, u, b, n, adj):
		unused = []
		dis = [float('inf')] * (n + 1)
		dis[u] = 0
		unused.append((0, u))
		heapify(unused)
		while unused:
			(x, v) = heappop(unused)
			if x > dis[v]:
				continue
			for edge in adj[v]:
				u = edge[0]
				w = edge[1]
				if dis[v] + w < dis[u]:
					dis[u] = dis[v] + w
					heappush(unused, (dis[u], u))
		return dis

	def shortestPath(self, n, m, a, b, edges):
		adj = [[] for i in range(n + 1)]
		curved = []
		for i in range(m):
			u = edges[i][0]
			v = edges[i][1]
			w = edges[i][2]
			cw = edges[i][3]
			adj[u].append((v, w))
			adj[v].append((u, w))
			curved.append([u, v, cw])
		da = self.dijkstra(a, b, n, adj)
		db = self.dijkstra(b, a, n, adj)
		ans = da[b]
		for i in range(m):
			u = curved[i][0]
			v = curved[i][1]
			cw = curved[i][2]
			ans = min(ans, da[u] + cw + db[v])
			ans = min(ans, da[v] + cw + db[u])
		if ans >= 1000000001:
			return -1
		return ans


import heapq

class Solution:

	def dij(self, a, n, m, adj):
		ans = [-1 for i in range(n + 1)]
		ans[a] = 0
		hq = []
		for (b, w) in adj[a]:
			hq.append((w, b))
		heapq.heapify(hq)
		while hq:
			(w, b) = heapq.heappop(hq)
			if ans[b] == -1:
				ans[b] = w
				for (b1, w1) in adj[b]:
					heapq.heappush(hq, (w + w1, b1))
		return ans

	def shortestPath(self, n, m, a, b, edges):
		adj = [[] for i in range(n + 1)]
		for (i, j, w1, w2) in edges:
			adj[i].append((j, w1))
			adj[j].append((i, w1))
		adis = self.dij(a, n, m, adj)
		if adis[b] == -1:
			return -1
		bdis = self.dij(b, n, m, adj)
		ans = adis[b]
		for (u, v, w1, w2) in edges:
			if adis[u] != -1 and adis[v] != -1:
				ans = min(ans, adis[u] + bdis[v] + w2, adis[v] + bdis[u] + w2)
		return ans


import heapq

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		adj = [[] for _ in range(2 * n + 1)]
		for [x, y, w1, w2] in edges:
			adj[x].append((y, w1))
			adj[y].append((x, w1))
			adj[x].append((y + n, w2))
			adj[y].append((x + n, w2))
			adj[x + n].append((y + n, w1))
			adj[y + n].append((x + n, w1))
		visited = [False] * (n * 2 + 1)
		visited[a + n] = True
		heap = [(0, a)]
		while heap:
			(d, i) = heapq.heappop(heap)
			if i == b or i == b + n:
				return d
			if visited[i]:
				continue
			visited[i] = True
			for (j, w) in adj[i]:
				if not visited[j]:
					heapq.heappush(heap, (d + w, j))
		return -1


import math
import heapq
import numpy as np

class Graph:

	def __init__(self, n, edges):
		self.edges = [dict() for _ in range(n + 1)]
		self.cu_edges = [dict() for _ in range(n + 1)]
		for e in edges:
			if e[0] in self.edges[e[1]]:
				self.edges[e[0]][e[1]] = min(e[2], self.edges[e[0]][e[1]])
				self.edges[e[1]][e[0]] = self.edges[e[0]][e[1]]
				self.cu_edges[e[0]][e[1]] = min(e[3], self.cu_edges[e[0]][e[1]])
				self.cu_edges[e[1]][e[0]] = self.cu_edges[e[0]][e[1]]
			elif e[0] != e[1]:
				self.edges[e[0]][e[1]] = e[2]
				self.edges[e[1]][e[0]] = e[2]
				self.cu_edges[e[1]][e[0]] = e[3]
				self.cu_edges[e[0]][e[1]] = e[3]

	def dijkstra(self, edges, cu_edges, src, t):
		pq = []
		disc = set()
		disc_cu = set()
		heapq.heappush(pq, (0, src, False))
		d = [[float('inf'), float('inf')] for i in range(n + 1)]
		d[src] = [0, 0]
		while pq:
			(cost, node, curve) = heapq.heappop(pq)
			if node in disc or (node in disc_cu and curve):
				continue
			disc_cu.add(node)
			if not curve:
				disc.add(node)
			if curve:
				for (to, p_cost) in edges[node].items():
					if to in disc_cu:
						continue
					d[to][1] = min(d[to][1], cost + p_cost)
					heapq.heappush(pq, (d[to][1], to, True))
			else:
				for (to, p_cost) in edges[node].items():
					if to in disc:
						continue
					d[to][0] = min(d[to][0], cost + p_cost)
					heapq.heappush(pq, (d[to][0], to, False))
				for (to, p_cost) in cu_edges[node].items():
					if to not in disc_cu:
						d[to][1] = min(d[to][1], cost + p_cost)
						heapq.heappush(pq, (d[to][1], to, True))
		return min(d[t]) if t in disc else -1

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		graph = Graph(n, edges)
		return graph.dijkstra(graph.edges, graph.cu_edges, a, b)


import math
import heapq

class Graph:

	def __init__(self, n, edges):
		self.st_edges = [dict() for _ in range(n + 1)]
		self.cu_edges = [dict() for _ in range(n + 1)]
		self.V = n
		for e in edges:
			if e[1] in self.st_edges[e[0]]:
				self.st_edges[e[0]][e[1]] = min(e[2], self.st_edges[e[0]][e[1]])
				self.st_edges[e[1]][e[0]] = min(e[2], self.st_edges[e[1]][e[0]])
			else:
				self.st_edges[e[0]][e[1]] = e[2]
				self.st_edges[e[1]][e[0]] = e[2]
			if e[1] in self.cu_edges[e[0]]:
				self.cu_edges[e[0]][e[1]] = min(e[3], self.cu_edges[e[0]][e[1]])
				self.cu_edges[e[1]][e[0]] = min(e[3], self.cu_edges[e[1]][e[0]])
			else:
				self.cu_edges[e[0]][e[1]] = e[3]
				self.cu_edges[e[1]][e[0]] = e[3]

	def dijkstra(self, n, edges, cu_edges, s, t):
		pq = []
		disc = set()
		disc_cu = set()
		d = [[float('inf'), float('inf')] for _ in range(n + 1)]
		d[s] = [0, 0]
		heapq.heappush(pq, (0, s, False))
		while pq:
			(cost, node, cu_path) = heapq.heappop(pq)
			if node in disc or (cu_path and node in disc_cu):
				continue
			if not cu_path:
				disc.add(node)
			disc_cu.add(node)
			if cu_path:
				for (to, p_cost) in edges[node].items():
					if to not in disc_cu:
						d[to][1] = min(d[to][1], cost + p_cost)
						heapq.heappush(pq, (d[to][1], to, True))
			else:
				for (to, p_cost) in edges[node].items():
					if to not in disc:
						d[to][0] = min(d[to][0], cost + p_cost)
						heapq.heappush(pq, (d[to][0], to, False))
				for (to, p_cost) in cu_edges[node].items():
					if to not in disc_cu:
						d[to][1] = min(d[to][1], cost + p_cost)
						heapq.heappush(pq, (d[to][1], to, True))
		return min(d[t][0], d[t][1]) if t in disc else -1

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		graph = Graph(n, edges)
		dst = graph.dijkstra(n, graph.st_edges, graph.cu_edges, a, b)
		return dst


from heapq import heappop, heappush
from math import inf

class Solution:

	def dijkstra(self, graph, src):
		n = len(graph)
		dist = [inf] * n
		dist[src] = 0
		heap = [(dist[src], src)]
		while heap:
			(d, u) = heappop(heap)
			if dist[u] < d:
				continue
			for (v, wt) in graph[u]:
				if dist[v] > dist[u] + wt:
					dist[v] = dist[u] + wt
					heappush(heap, (dist[v], v))
		return dist

	def shortestPath(self, n, m, a, b, edges):
		graph = [[] for _ in range(n)]
		for (u, v, w1, _) in edges:
			graph[u - 1].append((v - 1, w1))
			graph[v - 1].append((u - 1, w1))
		dista = self.dijkstra(graph, a - 1)
		distb = self.dijkstra(graph, b - 1)
		res = dista[b - 1]
		for (u, v, _, w2) in edges:
			res = min(res, dista[u - 1] + w2 + distb[v - 1])
			res = min(res, distb[u - 1] + w2 + dista[v - 1])
		return res if res != inf else -1


from collections import defaultdict

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		g = defaultdict(list)
		for (n1, n2, x, y) in edges:
			g[n1].append([n2, x, y])
			g[n2].append([n1, x, y])
		val1 = [float('inf') for i in range(n + 1)]
		val2 = [float('inf') for i in range(n + 1)]
		val1[a] = 0
		val2[b] = 0
		h = []
		heappush(h, [0, a])
		while h:
			(t, node) = heappop(h)
			for (child, x, y) in g[node]:
				if val1[child] > t + x:
					val1[child] = t + x
					heappush(h, [val1[child], child])
		h = []
		heappush(h, [0, b])
		while h:
			(t, node) = heappop(h)
			for (child, x, y) in g[node]:
				if val2[child] > t + x:
					val2[child] = t + x
					heappush(h, [val2[child], child])
		ans = min(val1[b], val2[a])
		for (n1, n2, x, y) in edges:
			ans = min(ans, val1[n1] + val2[n2] + y)
			ans = min(ans, val2[n1] + val1[n2] + y)
		if ans > 1000000000000.0:
			return -1
		return ans


from heapq import heappop, heappush

class Node:

	def __init__(self, i):
		self.ID = i
		self.out = []
		self.is_visited = False

	def __lt__(self, other):
		return self.ID < other.ID

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		N = 2 * n + 1
		we = [[] for i in range(N)]
		for (x, y, w1, w2) in edges:
			we[x].append((y, w1))
			we[y].append((x, w1))
			we[x + n].append((y + n, w1))
			we[y + n].append((x + n, w1))
			we[x].append((y + n, w2))
			we[y].append((x + n, w2))
		visited = [False] * N
		visited[a + n] = True
		q = [(0, a)]
		while q:
			(dist, u) = heappop(q)
			if u == b or u == b + n:
				return dist
			if visited[u]:
				continue
			visited[u] = True
			for (v, w) in we[u]:
				if not visited[v]:
					heappush(q, (dist + w, v))
		return -1


import heapq

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		import heapq
		import sys

		def buildAdjList(n, edges):
			l = [[] for i in range(n)]
			for edge in edges:
				(x, y, w1, w2) = edge
				l[x - 1].append([y - 1, w1])
				l[y - 1].append([x - 1, w1])
			return l

		def existPath(x):
			return x != sys.maxsize

		def dijkstra(V, adj, S):
			pq = []
			dist = [sys.maxsize for i in range(V)]
			used = [False for i in range(V)]
			heapq.heappush(pq, (0, S))
			while len(pq) > 0:
				(d, u) = heapq.heappop(pq)
				if used[u]:
					continue
				dist[u] = d
				used[u] = True
				for x in adj[u]:
					(v, w) = x
					if not used[v] and dist[v] > dist[u] + w:
						dist[v] = dist[u] + w
						heapq.heappush(pq, (dist[v], v))
			return (dist, used)
		l = buildAdjList(n, edges)
		(dista, _) = dijkstra(n, l, a - 1)
		minCost = dista[b - 1]
		if existPath(dista[b - 1]):
			(distb, _) = dijkstra(n, l, b - 1)
			for e in edges:
				(x, y, w1, w2) = e
				if existPath(dista[x - 1]) and existPath(distb[y - 1]):
					minCost = min(minCost, dista[x - 1] + w2 + distb[y - 1])
				if existPath(dista[y - 1]) and existPath(distb[x - 1]):
					minCost = min(minCost, dista[y - 1] + w2 + distb[x - 1])
		else:
			return -1
		if minCost == sys.maxsize:
			return -1
		return minCost


from heapq import heappush, heappop
INF = float('inf')

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		from collections import defaultdict
		cu = []
		g = defaultdict(list)
		for (x, y, w1, w2) in edges:
			g[x].append((y, w1))
			g[y].append((x, w1))
			cu.append((x, y, w2))

		def dijkstra(x, y):
			nonlocal n, g
			ret = [INF] * (n + 1)
			ret[x] = 0
			q = [(0, x)]
			while q:
				(cost0, n0) = heappop(q)
				for (nbr, w) in g[n0]:
					cost = cost0 + w
					if ret[nbr] > cost:
						ret[nbr] = cost
						heappush(q, (cost, nbr))
			return ret
		da = dijkstra(a, b)
		db = dijkstra(b, a)
		ans = da[b]
		for (u, v, w) in cu:
			ans = min(ans, da[u] + w + db[v])
			ans = min(ans, da[v] + w + db[u])
		return -1 if ans == INF else ans


import heapq, collections

def dijkstra(source, adj, n):
	minheap = [[0, source]]
	heapq.heapify(minheap)
	vis = set()
	l = 0
	arr = [float('inf') for i in range(n + 1)]
	while minheap:
		(w1, n1) = heapq.heappop(minheap)
		if arr[n1] > w1:
			arr[n1] = w1
		else:
			continue
		for (n2, w2) in adj[n1]:
			if arr[n2] > w1 + w2:
				heapq.heappush(minheap, [w1 + w2, n2])
	return arr

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		route = collections.defaultdict(list)
		for (x, y, w1, w2) in edges:
			route[x].append([y, w1])
			route[y].append([x, w1])
		dist_a = dijkstra(a, route, n)
		dist_b = dijkstra(b, route, n)
		mina = dist_a[b]
		for (x, y, w1, w2) in edges:
			mina = min(mina, dist_a[x] + w2 + dist_b[y])
			mina = min(mina, dist_a[y] + w2 + dist_b[x])
		if mina == float('inf'):
			return -1
		return mina


import heapq as hq

class Solution:

	def shortestPath(self, n, m, a, b, edges):
		inf = 1000000000.0

		def dijkstra(src):
			dists = [inf for i in range(n)]
			dists[src] = 0
			heap = [(0, src)]
			while heap:
				(d, cur) = hq.heappop(heap)
				for (neigh, w, cw) in graph[cur]:
					if dists[neigh] > dists[cur] + w:
						dists[neigh] = dists[cur] + w
						hq.heappush(heap, (dists[neigh], neigh))
			return dists
		graph = {i: [] for i in range(n)}
		for (x, y, w, cw) in edges:
			graph[x - 1].append((y - 1, w, cw))
			graph[y - 1].append((x - 1, w, cw))
		a_dists = dijkstra(a - 1)
		b_dists = dijkstra(b - 1)
		res = a_dists[b - 1]
		for (x, y, w, cw) in edges:
			res = min([res, a_dists[x - 1] + cw + b_dists[y - 1], a_dists[y - 1] + cw + b_dists[x - 1]])
		return res if res < inf else -1


import heapq

class Solution:

	def dijkstra(self, a, b, n, adj):
		dist = [float('inf')] * (n + 1)
		pq = [(0, a)]
		dist[a] = 0
		while pq:
			(dis, node) = heapq.heappop(pq)
			for (v, wt) in adj[node]:
				if dist[v] > dist[node] + wt:
					dist[v] = dist[node] + wt
					heapq.heappush(pq, (dist[v], v))
		return dist

	def shortestPath(self, n, m, a, b, edges):
		adj = [[] for i in range(n + 1)]
		curved = []
		for (u, v, wt, cwt) in edges:
			adj[u].append((v, wt))
			adj[v].append((u, wt))
			curved.append([u, v, cwt])
		dist1 = self.dijkstra(a, b, n, adj)
		dist2 = self.dijkstra(b, a, n, adj)
		ans = dist1[b]
		for (u, v, cwt) in curved:
			ans = min(ans, dist1[u] + cwt + dist2[v])
			ans = min(ans, dist1[v] + cwt + dist2[u])
		if ans >= float('inf'):
			return -1
		return ans