1:   

   2:  #include <iostream> 

   3:  #include <vector>

   4:  #include <algorithm>

   5:  #include <queue>

   6:  #include <string.h>

   7:  #include <stdio.h>

   8:  using namespace std;

   9:   

  10:  #define V   1005

  11:  #define E   100005

  12:  #define INF 329999         

  13:   

  14:  // v :the end point of an edge. w : the weight of the weight next:cluster according to the begin point of the edge

  15:  struct node

  16:  {

  17:      int v, w,next;

  18:      node(int vv=0, int ww=0):v(vv),w(ww){}

  19:      bool operator < (const node& r) const{return w> r.w;}

  20:  }pnt[E],pnt1[E];

  21:   

  22:  int e=0,N,M,s;

  23:   

  24:  int head[V];

  25:  int dis[V];

  26:  bool vis[V];

  27:  int src, sink;

  28:   

  29:  void Dijkstra()

  30:  { 

  31:      priority_queue<node> Q; 

  32:      vis[src] = 1; dis[src] = 0; 

  33:      Q.push(node(src, 0)); 

  34:      for (int u = src, i=1; i< N; i++)                 

  35:      { 

  36:          for (int j = head[u]; j != -1; j = pnt[j].next)    // j is edge number.

  37:          { 

  38:              int v = pnt[j].v;                          

  39:              if (vis[v] == 0 && dis[v] > dis[u] + pnt[j].w )// pre is the current vertex

  40:              { 

  41:                  dis[v] = dis[u] + pnt[j].w; 

  42:                  Q.push(node(v, dis[v]));

  43:              } 

  44:          } 

  45:          while (!Q.empty() && vis[Q.top().v]) Q.pop(); 

  46:          if (Q.empty()) break;

  47:          vis[u = Q.top().v] = 1; Q.pop();

  48:      }

  49:  } 

  50:  int head1[V];

  51:  inline void addedge1(int u, int v, int w)

  52:  {

  53:      pnt1[s].v =v; pnt1[s].w = w; pnt1[s].next = head1[u]; head1[u]=s++;

  54:  }

  55:  inline void addedge(int u, int v, int w){ 

  56:      pnt[e].v = v; pnt[e].w = w; pnt[e].next= head[u]; head[u]=e++;

  57:  } 

  58:   

  59:  void Dijkstra_init()

  60:  { 

  61:      e = 0; s =0;

  62:      memset(head, -1, sizeof(head)); 

  63:      memset(head1, -1, sizeof(head));

  64:      memset(vis, 0, sizeof(vis));

  65:      scanf("%d%d", &N , &M);

  66:      for (int i = 0; i <=N; i++) dis[i] = INF; 

  67:      scanf("%d", &src);

  68:      //cout<<src<<endl;

  69:      for(int i=0; i<M; i++)

  70:      {

  71:          int a, b, c;

  72:          scanf("%d%d%d", &a, &b, &c);

  73:          addedge(a, b, c);

  74:          addedge1(b,a, c);

  75:      }

  76:   

  77:   

  78:  } 

  79:   

  80:  int main()

  81:  {

  82:      //freopen("3268.txt","r",stdin);

  83:   

  84:      Dijkstra_init();

  85:      Dijkstra();

  86:      int dis1[V];

  87:      for(int i=0; i<=N; i++) dis1[i] = dis[i];

  88:      //for(int i=1; i<=N; i++) cout<<dis[i]<<" "; cout<<endl;

  89:      memset(vis, 0 ,sizeof(vis));

  90:      for(int i=0; i<=N; i++) { dis[i]= INF; head[i] = head1[i];}

  91:      for(int i=0; i<M; i++)

  92:      {

  93:          pnt[i]=pnt1[i];

  94:   

  95:      }

  96:      Dijkstra();

  97:      //for(int i=1; i<=N; i++) cout<<dis[i]<<" "; cout<<endl;

  98:      int ret = 0;

  99:      for(int i=1; i<=N; i++) ret = max(ret, dis1[i]+dis[i]);

 100:      cout<<ret<<endl;

 101:      return 0;

 102:  }

 103: