SHARE
TWEET

Untitled

a guest Jan 20th, 2020 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define N 100005
  3. #define f first
  4. #define s second
  5. #define pb push_back
  6. using namespace std;
  7. typedef pair<int,int> pii;
  8. typedef long long ll;
  9. const long long INF = 1000000000000000000ll;
  10.  
  11. vector<pii> graf[N], GT[N];//para {u,nr}
  12. pii kr[2*N];
  13. ll odlStart[N], odlKoniec[N];
  14. int path[N];//poprzednik wierzcholka [v] na drodze 1 -> n
  15. int isOnPath[2*N];//czy ita krawedz jest na sciezce 1 -> n
  16.  
  17. int n, m, waga[2*N];//waga itej krawedzi
  18. priority_queue<pair<long long, int>> Q;
  19.  
  20.  
  21. void wczytaj() {
  22.     cin>>n>>m;
  23.     for(int i= 1; i <= m; i++) {
  24.         int v, u, c;
  25.         cin>>v>>u>>c;
  26.         graf[v].pb({u,i});
  27.         GT[u].pb({v,i});
  28.         waga[i] = c;
  29.         kr[i] = {v,u};
  30.     }
  31. }
  32.  
  33. void dijkstra1() {
  34.     for(int i = 1; i <= n; i++)
  35.         odlStart[i] = INF;
  36.     odlStart[1] = 0;
  37.     Q.push({0,1});
  38.     while(Q.size()) {
  39.         int v = Q.top().second;
  40.         ll dist = Q.top().first * (-1);
  41.         Q.pop();
  42.         if(dist > odlStart[v])
  43.             continue;
  44.         for(auto it: graf[v]) {
  45.             int u = it.f, kraw = waga[it.s];
  46.             if(dist + kraw < odlStart[u]) {
  47.                 odlStart[u] = dist + kraw;
  48.                 path[u] = v;
  49.                 Q.push({-odlStart[u],u});
  50.             }
  51.         }
  52.     }
  53. //  for(int i = 1; i <= n; i++)
  54. //      cout<<"v="<<i<<" odl="<<odlStart[i]<<" path="<<path[i]<<"\n";
  55. }
  56.  
  57. void dijkstra2() {
  58.     for(int i = 1; i <= n; i++)
  59.         odlKoniec[i] = INF;
  60.     odlKoniec[n] = 0;
  61.     Q.push({0,n});
  62.     while(Q.size()) {
  63.         int v = Q.top().second;
  64.         ll dist = Q.top().first * (-1);
  65.         Q.pop();
  66.         if(dist > odlKoniec[v])
  67.             continue;
  68.         for(auto it: GT[v]) {
  69.             int u = it.f, kraw = waga[it.s];
  70.             if(dist + kraw < odlKoniec[u]) {
  71.                 odlKoniec[u] = dist + kraw;
  72.                 Q.push({-odlKoniec[u],u});
  73.             }
  74.         }
  75.     }
  76. //  for(int i = 1; i <= n; i++)
  77. //      cout<<"v="<<i<<" odlKoniec="<<odlKoniec[i]<<"\n";
  78. }
  79.  
  80. void sciezka() {
  81.     int v = n;
  82.     while(v != 1) {
  83.         int u = path[v];
  84.         for(auto it: graf[u])
  85.             if(it.f == v)
  86.                 isOnPath[it.s] = 1;
  87.         v = u;
  88.     }
  89. //  for(int i = 1; i <= m; i++)
  90. //      cout<<"i="<<i<<" isOnPath="<<isOnPath[i]<<"\n";
  91. }
  92.  
  93. void findAns() {
  94.     ll ans = INF;
  95.     for(int i = 1; i <= m; i++)
  96.         if(isOnPath[i] == 0) {
  97.             int v = kr[i].f, u = kr[i].s;
  98.             if(odlStart[v] + odlKoniec[u] + waga[i] < ans)
  99.                 ans = odlStart[v] + odlKoniec[u] + waga[i];
  100.         }
  101.     if(ans == INF)
  102.         cout<<"-1";
  103.     else
  104.         cout<<ans;
  105. }
  106.  
  107. int main() {
  108.     ios_base::sync_with_stdio(0);
  109.     wczytaj();
  110.     dijkstra1();
  111.     dijkstra2();
  112.     sciezka();
  113.     findAns();
  114.     return 0;
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top