fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 3e5 + 5;
  6. const long long oo = 1e18;
  7.  
  8. int n, m, s, t;
  9.  
  10. struct DATA{
  11.     int v, f, id;
  12. };
  13.  
  14. vector < DATA > E[N];
  15.  
  16. bool cmp(DATA A, DATA B){
  17.     return A.f < B.f;
  18. }
  19.  
  20. struct Graph{
  21.     int u, v, w, f;
  22. } a[N];
  23.  
  24. struct dinh{
  25.     int u, tp;
  26. };
  27.  
  28. vector < pair<dinh, long long> > G[N][2];
  29.  
  30. struct kmv{
  31.     long long du;
  32.     int u, tp;
  33.  
  34.     bool operator > (kmv A){
  35.         return du > A.du;
  36.     }
  37. };
  38.  
  39. long long d[N][2];
  40.  
  41. void dijkstra(){
  42.     for (int i = 1; i <= m; i ++)
  43.         d[i][0] = d[i][1] = oo;
  44.  
  45.     priority_queue <kmv, vector<kmv>, greater<> > pq;
  46.  
  47.     for (int i = 1; i <= m; i ++){
  48.         if (a[i].u == s){
  49.             d[i][0] = 0;
  50.             pq.push({0, i, 0});
  51.         }
  52.         else
  53.         if (a[i].v == s){
  54.             d[i][1] = 0;
  55.             pq.push({0, i, 1});
  56.         }
  57.     }
  58.  
  59.     while (pq.size()){
  60.         kmv val = pq.top();
  61.         pq.pop();
  62.  
  63.         long long du = val.du;
  64.         int u = val.u;
  65.         int tp = val.tp;
  66.  
  67.         if (du != d[u][tp])
  68.             continue;
  69.  
  70.         for (pair<dinh, long long> i : G[u][tp]){
  71.             int v = i.first.u;
  72.             int ntp = i.first.tp;
  73.             long long w = i.second;
  74.  
  75.             long long dv = du + w;
  76.  
  77.             if (d[v][ntp] > dv){
  78.                 d[v][ntp] = dv;
  79.                 pq.push({dv, v, ntp});
  80.             }
  81.         }
  82.     }
  83. }
  84.  
  85. void SOLVE(){
  86.     cin >> n >> m >> s >> t;
  87.  
  88.     for (int i = 1; i <= m; i ++){
  89.         int u, v, w, f;
  90.         cin >> u >> v >> w >> f;
  91.  
  92.         if (u > v)
  93.             swap(u, v);
  94.  
  95.         a[i] = {u, v, w, f};
  96.  
  97.         E[u].push_back({v, f, i});
  98.         E[v].push_back({u, f, i});
  99.  
  100.         G[i][0].push_back({{i, 1}, w});
  101.         G[i][1].push_back({{i, 0}, w});
  102.     }
  103.  
  104.     for (int i = 1; i <= n; i ++){
  105.         sort(E[i].begin(), E[i].end(), cmp);
  106.  
  107.         for (int j = 0; j + 1 < (int) E[i].size(); j ++){
  108.             int id1 = E[i][j].id;
  109.             int tp1 = -1;
  110.  
  111.             if (a[id1].u == i)
  112.                 tp1 = 0;
  113.             else
  114.                 tp1 = 1;
  115.  
  116.             int id2 = E[i][j + 1].id;
  117.             int tp2 = -1;
  118.  
  119.             if (a[id2].u == i)
  120.                 tp2 = 0;
  121.             else
  122.                 tp2 = 1;
  123.  
  124.             int w = E[i][j + 1].f - E[i][j].f;
  125.  
  126.             G[id1][tp1].push_back({{id2, tp2}, w});
  127.             G[id2][tp2].push_back({{id1, tp1}, w});
  128.         }
  129.     }
  130.  
  131.     dijkstra();
  132.  
  133.     long long ans = oo;
  134.  
  135.     for (int i = 1; i <= m; i ++)
  136.         if (a[i].u == t)
  137.             ans = min(ans, d[i][0]);
  138.         else
  139.         if (a[i].v == t)
  140.             ans = min(ans, d[i][1]);
  141.  
  142.     if (ans == oo)
  143.         ans = -1;
  144.  
  145.     cout << ans;
  146. }
  147.  
  148. signed main(){
  149.     ios_base::sync_with_stdio(0);
  150.     cin.tie(0); cout.tie(0);
  151.  
  152.     #define TASK "message"
  153.  
  154.     if (fopen(TASK".inp","r")){
  155.         freopen(TASK".inp","r",stdin);
  156.         freopen(TASK".out","w",stdout);
  157.     }
  158.  
  159.     int nTest = 1;
  160.  
  161.     while (nTest --){
  162.         SOLVE();
  163.     }
  164.  
  165.     return 0;
  166. }
Success #stdin #stdout 0.01s 29116KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/D6fntO
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!