洛谷 P1073 最优贸易 & [NOIP2009提高组]（反向最短路）

传送门

---

解题思路

很长的题，实际上在一个有向图（点有点权）中求一个从起点1到终点n的路径，使得这条路径上点权最大的点与点权最小的点的差值最大（要求必须从点权较小的点能够走到点权较大的点）。

——最短路？？

——不像呀。

（可是洛谷标签上写着呀）

就是一个写起来像最短路的一个图中的dp。

我们用dis1[i]表示从1号点到第i号点的路径上的最小值，用dis2[i]表示从i号点到第n号点的最大值，最后只需要找出最大的（dis2[i]-dis1[i]）即可。

怎么求dis2呢？这里有一种方法——建反图。

建反图就是把每一条有向边反过来，例如原来是u-->v，现在变成了v-->u。

然后从n开始，跑一遍n到各个点的最短路，求出dis2数组。

对于dis数组，dis[i的儿子k]=dis[i],v[k](k号点本身的数值),dis[k]中的最小值/最大值。

用dijkstra或者spfa跑一遍图就可以了。

当年，spfa还没有死去。

AC代码

 #include<iostream>

 #include<queue>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn=;

 const int maxm=;//注意有可能是双向边，所以要开两倍的数组。

 int n,m,p1[maxn],p2[maxn],cnt1,cnt2,vis[maxn],dis1[maxn],dis2[maxn],ans,v[maxn];

 struct edge{

     int v,next;

 }e1[maxm],e2[maxm];            //两个图

 void insert1(int u,int v){    //两个insert

     cnt1++;

     e1[cnt1].v=v;

     e1[cnt1].next=p1[u];

     p1[u]=cnt1;

 }

 void insert2(int u,int v){

     cnt2++;

     e2[cnt2].v=v;

     e2[cnt2].next=p2[u];

     p2[u]=cnt2;

 }

 struct node{

     int num,len;

 };

 bool operator < (node a,node b){

     return a.len>b.len;

 }

 priority_queue<node> q1,q2;

 void dijkstra1(){            //两个dijkstra

     memset(vis,,sizeof(vis));

     memset(dis1,0x3f,sizeof(dis1));

     dis1[]=v[];

     node nd;

     nd.len=v[];

     nd.num=;

     q1.push(nd);

     while(!q1.empty()){

         node u=q1.top();

         q1.pop();

         if(vis[u.num]) continue;

         vis[u.num]=;

         for(int i=p1[u.num];i!=-;i=e1[i].next){

             dis1[e1[i].v]=min(min(dis1[e1[i].v],u.len),v[e1[i].v]);//算是个小的dp吧

             node xin;

             xin.num=e1[i].v;

             xin.len=dis1[e1[i].v];

             q1.push(xin);

         }

     }

 }

 void dijkstra2(){

     memset(vis,,sizeof(vis));

     memset(dis2,-0x3f,sizeof(dis2));

     dis2[n]=v[n];

     node nd;

     nd.len=v[n];

     nd.num=n;

     q2.push(nd);

     while(!q2.empty()){

         node u=q2.top();

         q2.pop();

         if(vis[u.num]) continue;

         vis[u.num]=;

         for(int i=p2[u.num];i!=-;i=e2[i].next){

             dis2[e2[i].v]=max(max(dis2[e2[i].v],u.len),v[e2[i].v]);

             node xin;

             xin.num=e2[i].v;

             xin.len=dis2[e2[i].v];

             q2.push(xin);

         }

     }

 }

 int main(){

     cin>>n>>m;

     memset(p1,-,sizeof(p1));

     memset(p2,-,sizeof(p2));

     for(int i=;i<=n;i++) cin>>v[i];

     for(int i=;i<=m;i++){

         int x,y,z;

         scanf("%d%d%d",&x,&y,&z);

         if(z==){

             insert1(x,y);

             insert2(y,x);

         }else{

             insert1(x,y);

             insert1(y,x);

             insert2(x,y);

             insert2(y,x);

         }

     }

     dijkstra1();

     dijkstra2();

     for(int i=;i<=n;i++) ans=max(ans,dis2[i]-dis1[i]);//求出答案

     cout<<ans;

     return ;

 }

//NOIP2009提高组t3

//好困啊，zzz

洛谷 P1073 最优贸易 & [NOIP2009提高组]（反向最短路）的相关教程结束。