1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
|
#include <bits/stdc++.h> using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL); #define mem(i,j) memset(i,j,sizeof (i)); using ll = int64_t; using ull = uint64_t; using ld = long double; using uint = uint32_t; const double EPS = 1e-8; const int INF = 0x3F3F3F3F; const ll LINF = 4611686018427387903; const int MOD = 1e9+7;
struct edg { int v, c, p; };
signed main() { EmiliaMyWife
int n, m, a, b, d; cin >> n >> m >> a >> b >> d; vector<vector<edg>> edge(n + 1); for(int i = 0, x, y, a, b, c, p; i < m; i++) cin >> x >> y >> a >> b >> c >> p, edge[x].push_back({y, a, b}), edge[y].push_back({x, c, p}); vector<int> dis, dis2; auto dijkstra = [&](int a, vector<int> &dis, int d) { dis = vector<int>(n + 1, INF); dis[a] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, a}); while(!pq.empty()) { auto [c, u] = pq.top(); pq.pop(); if(dis[u] < c) continue; for(auto &x : edge[u]) { int cost = x.c + x.p * d; if(c + cost < dis[x.v]) { dis[x.v] = c + cost; pq.push({dis[x.v], x.v}); } } } }; dijkstra(a, dis, 0), dijkstra(b, dis2, 0); int ans = dis[b] + dis2[a]; dijkstra(a, dis, d - 1), dijkstra(b, dis2, d - 1); cout << min(ans, dis[b] + dis2[a]) << '\n';
return 0; }
|