fork download
copy 
  1. #include "crocodile.h"
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. #define MAXN 100005
  7. typedef pair<int,int> pii;
  8.  
  9. static int N,DF[MAXN],DS[MAXN],V[MAXN];
  10. static vector<int> con[MAXN],conv[MAXN];
  11. static priority_queue<pii> que;
  12.  
  13. int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
  14. {
  15.     int i,k,v,q,a,b,c;
  16.     N = n;
  17.     for (i=0;i<m;i++){
  18.         a = R[i][0]+1, b = R[i][1]+1, c = L[i];
  19.         con[a].push_back(b), conv[a].push_back(c);
  20.         con[b].push_back(a), conv[b].push_back(c);
  21.     }
  22.     for (i=1;i<=N;i++) DF[i] = DS[i] = 2e9;
  23.     for (i=0;i<K;i++){
  24.         k = P[i]+1;
  25.         DF[k] = DS[k] = 0;
  26.         que.push(pii(0,k));
  27.     }
  28.     while (!que.empty()){
  29.         q = que.top().second; que.pop();
  30.         if (V[q]) continue;
  31.         V[q] = 1;
  32.         for (i=con[q].size();i--;){
  33.             k = con[q][i]; v = conv[q][i];
  34.             if (V[k]) continue;
  35.             if (DF[k] > DS[q]+v){
  36.                 DS[k] = DF[k], DF[k] = DS[q]+v;
  37.                 if (DS[k] < 2e9) que.push(pii(-DS[k],k));
  38.             }
  39.             else if (DS[k] > DS[q]+v){
  40.                 DS[k] = DS[q]+v;
  41.                 que.push(pii(-DS[k],k));
  42.             }
  43.         }
  44.     }
  45.     return DS[1];
  46. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VyRwKZ
language:
C++ (gcc 8.3)
created:
10 years 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!