题目大意：给出一个单向带权图和一个点s，求点u，u到s的最短路径和s到u的最短路径之和最大。

对于s到任意点的最短路，直接dijkstra可以求出。

对于任意点到s的最短路，如果将所有边反向然后求一次最短路，容易证明，求出的s到任意点v的最短路s-->v就是原来没有反向的图的v-->s的最短路。

所以先求一次dijkstra，保存此次的结果，然后把所有的边反向，权值不变，再求一次dijkstra，将两次结果加起来，计算它们之中的最大值。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int maxn=1010; const int INF=(1<<29); struct edge { int to; int dis; }; struct edge2 { int from; int to; int dis; }; struct heapnode { int di; int num; bool operator< (const heapnode j) const { return di>j.di; } }; edge2 e[100010]; int d[maxn]; int sum[maxn]; int use[maxn]; int n; vector
      
        G[maxn]; void dijkstra(int s); int main(void) { int i,u,v,p,q,m,ans; edge ed; while(scanf("%d%d%d",&n,&m,&q)==3) { for(i=1;i<=n;i++) { G[i].clear(); } for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&p); ed.to=v; ed.dis=p; G[u].push_back(ed); e[i].from=u; e[i].to=v; e[i].dis=p; } dijkstra(q); for(i=1;i<=n;i++) { sum[i]=d[i]; G[i].clear(); } for(i=1;i<=m;i++) { ed.to=e[i].from; ed.dis=e[i].dis; G[e[i].to].push_back(ed); } dijkstra(q); ans=0; for(i=1;i<=n;i++) { ans=d[i]+sum[i]>ans?d[i]+sum[i]:ans; } printf("%d\n",ans); } return 0; } void dijkstra(int s) { int i,u,p; heapnode h; priority_queue
       
         heap; for(i=1;i<=n;i++) { d[i]=INF; use[i]=0; } h.di=0; h.num=s; d[s]=0; heap.push(h); while(heap.empty()==false) { h=heap.top(); heap.pop(); u=h.num; if(use[u]==0) { use[u]=1; p=G[u].size(); for(i=0;i