#include #include #include using namespace std; #define maxN 100005 int n, m, d, r; vector hrany[2 * maxN]; vector delka[2 * maxN]; long long vzdalenost[2 * maxN]; bool zpracovany[2 * maxN]; int main() { scanf("%d%d%d%d", &n, &m, &d, &r); --d; --r; // Vrcholy interně číslujeme od nuly. for (int i = 0; i < m; ++i) { int a, b, pesky, konem; scanf("%d%d%d%d", &a, &b, &pesky, &konem); --a; --b; // Vrcholy interně číslujeme od nuly. // Vrchol 2*a odpovídá vrcholu pro chození pěšky, 2*a+1 pro jízdu na koni. for (int k = 0; k < 2; ++k) { int delka_hrany = (k == 0) ? pesky : konem; hrany[2 * a + k].push_back(2 * b + k); delka[2 * a + k].push_back(delka_hrany); hrany[2 * b + k].push_back(2 * a + k); delka[2 * b + k].push_back(delka_hrany); } } int s; scanf("%d", &s); for (int i = 0; i < s; ++i) { int x; scanf("%d", &x); --x; hrany[2 * x].push_back(2 * x + 1); delka[2 * x].push_back(0); hrany[2 * x + 1].push_back(2 * x); delka[2 * x + 1].push_back(0); } // Dijkstrův algoritmus na hledání nejkratší cesty. for (int i = 0; i < 2 * n; ++i) { zpracovany[i] = false; vzdalenost[i] = -1; // K vrcholu se zatim neda dostat. } // Do haldy dáváme dvojice (-vzdálenost, index vrcholu), protože // priority_queue třídí primárně podle první slozky a preferuje větší čísla. priority_queue > fronta; fronta.push(make_pair(0, 2 * d)); vzdalenost[2 * d] = 0; while (!fronta.empty()) { int u = fronta.top().second; fronta.pop(); if (u == 2 * r) break; // Vrchol, do kterého se chceme dostat, už je hotový. if (zpracovany[u]) continue; // Vrchol už jsme jednou zpracovali. zpracovany[u] = true; for (int i = 0; i < hrany[u].size(); ++i) { int v = hrany[u][i]; // Našli jsme první nebo kratší cestu do vrcholu v. if (vzdalenost[v] == -1 || vzdalenost[u] + delka[u][i] < vzdalenost[v]) { vzdalenost[v] = vzdalenost[u] + delka[u][i]; fronta.push(make_pair(-vzdalenost[v], v)); } } } printf("%lld\n", vzdalenost[2 * r]); return 0; }