题目链接：

思路：题目的意思是求S->T的所有路径中花费总和小于给定的P值的所经过的路径上的最大权值。我们可以从起点做一次SPFA,然后求出起点到所有点的最短路径，然后以终点为起点，将边反向，求终点到起点的最短路，然后枚举每一条边即可，求最大值。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define MAXN 22222 8 #define MAXM 222222 9 #define inf 1<<3010 #define FILL(a,b) memset(a,b,sizeof(a))11 12 template
           
            inline T Get_Min(const T &a,const T &b){ return a
            
             inline T Get_Max(const T &a,const T &b){ return a>b?a:b; }14 struct Edge{15 int v,w,next;16 }edge1[MAXM],edge2[MAXM];17 18 int n,m,st,ed,p,NE1,NE2;19 int head1[MAXN],head2[MAXN];20 21 void Insert1(int u,int v,int w)22 {23 edge1[NE1].v=v;24 edge1[NE1].w=w;25 edge1[NE1].next=head1[u];26 head1[u]=NE1++;27 }28 29 void Insert2(int u,int v,int w)30 {31 edge2[NE2].v=v;32 edge2[NE2].w=w;33 edge2[NE2].next=head2[u];34 head2[u]=NE2++;35 }36 37 int dist[2][MAXN];38 bool mark[MAXN];39 void spfa(int st,int ed,Edge *edge,int *dist,int *head)40 {41 FILL(mark,false);42 fill(dist,dist+n+2,inf);43 queue
             
              que;44 que.push(st);45 dist[st]=0;46 while(!que.empty()){47 int u=que.front();48 que.pop();49 mark[u]=false;50 for(int i=head[u];i!=-1;i=edge[i].next){51 int v=edge[i].v,w=edge[i].w;52 if(dist[u]+w