[关闭]
@TryMyEdge 2017-02-22T07:12:08.000000Z 字数 7947 阅读 916

专题九(最短路)

题解

题目

A 最短路

题目大意：

    有N(N<=100)个路口，M(M<=10000)条连接两个路口的无向路，第i条路连接Ai和Bi，要花Ci(1<=Ci<=1000)通过。问从1号路口到N号路口最少花多少时间。题目保证1能走到N。
    多组数据。

解题思路：

    按输入建边，因为用的储存图的方法是链式前向星，所以把一条无向边拆成两条反向的有向边储存。然后以1为起点跑spfa。最终答案是到N的距离。
    时间复杂度o(k*M)，空间复杂度o(M)。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #define pq priority_queue
  4. #define Pi acos(-1.0)
  5. using namespace std;
  6. #define MOD 1000000007
  7. struct Edge
  8. {
  9.     int to,d;
  10. }edges[200005];
  11. int pre[100005];
  12. int dis[105];
  13. bool life[105];
  14. int root[105];
  15. queue <int> q;
  16. int main()
  17. {
  18.     int n,m,now,temp;
  19.     while(scanf("%d%d",&n,&m),n || m)
  20.     {
  21.         memset(root,0,sizeof(root));
  22.         life[1]=1;
  23.         dis[1]=0;
  24.         q.push(1);
  25.         for(int i=2;i<=n;i++)
  26.             dis[i]=666666;
  27.         for(int i=1;i<=m;i++)
  28.         {
  29.             scanf("%d%d%d",&edges[i].to,&edges[i+m].to,&edges[i].d);
  30.             edges[i+m].d=edges[i].d;
  31.             pre[i]=root[edges[i+m].to];
  32.             root[edges[i+m].to]=i;
  33.             pre[i+m]=root[edges[i].to];
  34.             root[edges[i].to]=i+m;
  35.         }
  36.         while(!q.empty())
  37.         {
  38.             now=q.front();
  39.             q.pop();
  40.             life[now]=0;
  41.             temp=root[now];
  42.             while(temp)
  43.             {
  44.                 if(dis[now]+edges[temp].d<dis[edges[temp].to])
  45.                 {
  46.                     dis[edges[temp].to]=dis[now]+edges[temp].d;
  47.                     if(!life[edges[temp].to])
  48.                     {
  49.                         life[edges[temp].to]=1;
  50.                         q.push(edges[temp].to);
  51.                     }
  52.                 }
  53.                 temp=pre[temp];
  54.             }
  55.         }
  56.         printf("%d\n",dis[n]);
  57.     }
  58.     return 0;
  59. }

B Wormholes

题目大意：

    农场里有N(1<=N<=500)块地，有M(1<=M<=2500)条双向路，第i条路连接S1i和E1i，通过所需时间为T1i(T1i<=10000)秒，有W(1<=W<=200)个虫洞，第i个虫洞从S2i通向E2i，能让时间退回T2i(T2i<=10000)秒之前。问能不能从某块地出发，回到这块地的时候时间比出发的时间早。两块地之间可能有多条路或者虫洞连接。
    F(1<=F<=5)组数据。

解题思路：

    从某个点出发回到这个点的时候时间比出发时间早，实际上就是说这个环的路径长度为负数，我们要找的就是图中有没有负环。spfa中一个点的最短距离如果被更新了，就要进队等待松弛，如果图中没有负环，那么一个点不可能被松弛超过N次。所以可以通过记录每个点进队的次数，来判断图中有没有负环。
    小细节：链式前向星等以边为单位储存图的方式是不用担心重边的。用spfa判断负环，跑完一组数据队列可能是没有清空的，初始化的时候要注意。
    时间复杂度o(F*N*M)，空间复杂度o(M)。

AC代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<queue>
  5. #define pq priority_queue
  6. #define Pi acos(-1.0)
  7. using namespace std;
  8. #define MOD 1000000007
  9. struct Edge
  10. {
  11.     int to,d;
  12. }edges[5205];
  13. int pre[5205];
  14. int dis[505];
  15. bool life[505];
  16. int nums[505];
  17. int root[505];
  18. queue <int> q;
  19. int main()
  20. {
  21.     int n,m,w,T,temp,now;
  22.     bool flag;
  23.     cin>>T;
  24.     while(T--)
  25.     {
  26.         flag=0;
  27.         while(!q.empty()) q.pop();
  28.         scanf("%d%d%d",&n,&m,&w);
  29.         memset(life,0,sizeof(life));
  30.         memset(root,0,sizeof(root));
  31.         memset(nums,0,sizeof(nums));
  32.         for(int i=1;i<=n;i++)
  33.             dis[i]=6666666;
  34.         for(int i=1;i<=m;i++)
  35.         {
  36.             scanf("%d%d%d",&edges[i].to,&edges[i+m].to,&edges[i].d);
  37.             edges[i+m].d=edges[i].d;
  38.             pre[i]=root[edges[i+m].to];
  39.             root[edges[i+m].to]=i;
  40.             pre[i+m]=root[edges[i].to];
  41.             root[edges[i].to]=i+m;
  42.         }
  43.         for(int i=2*m+1;i<=2*m+w;i++)
  44.         {
  45.             scanf("%d%d%d",&temp,&edges[i].to,&edges[i].d);
  46.             edges[i].d=-edges[i].d;
  47.             pre[i]=root[temp];
  48.             root[temp]=i;
  49.         }
  50.         for(int i=1;i<=n;i++)
  51.         {
  52.             if(dis[i]!=6666666)
  53.                 continue;
  54.             dis[i]=0;
  55.             q.push(i);
  56.             life[i]=1;
  57.             while(!q.empty())
  58.             {
  59.                 now=q.front();
  60.                 nums[now]++;
  61.                 if(nums[now]>n)
  62.                 {
  63.                     flag=1;
  64.                     break;
  65.                 }
  66.                 q.pop();
  67.                 life[now]=0;
  68.                 temp=root[now];
  69.                 while(temp)
  70.                 {
  71.                     if(dis[now]+edges[temp].d<dis[edges[temp].to])
  72.                     {
  73.                         dis[edges[temp].to]=dis[now]+edges[temp].d;
  74.                         if(!life[edges[temp].to])
  75.                         {
  76.                             life[edges[temp].to]=1;
  77.                             q.push(edges[temp].to);
  78.                         }
  79.                     }
  80.                     temp=pre[temp];
  81.                 }
  82.             }
  83.             if(flag)
  84.                 break;
  85.         }
  86.         if(flag)
  87.             printf("YES\n");
  88.         else
  89.             printf("NO\n");
  90.     }
  91.     return 0;
  92. }

C Stockbroker Grapevine

题目大意：

    有m个经纪人，第i个人可以把信息传递给其他ni(0<=ni<m)个经纪人，传递给其中第j个人需要花tij(1<=tij<=100)时间。问选定其中一个人，能否让所有经纪人都得到这个信息，如果能，选谁所花的时间最短，时间最短是多少。
    多组数据。

解题思路：

    如果确定了起点，那么让所有人都得到这个消息的时间，就是离这个点最远的那个点的距离。用floyd算法求出任意两点的最短距离，然后对于每一个起点看哪个点离他最远，就可以知道选这个点为起点对应的所需时间。枚举起点更新答案即可。
    小细节：预处理一个非常大的数字表示+∞，最终答案如果等于预处理的这个数字 那么说明没有点可以连通所有点。
    时间复杂度o(m^3)，空间复杂度o(m^2)。

AC代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<queue>
  5. #define pq priority_queue
  6. #define Pi acos(-1.0)
  7. using namespace std;
  8. #define MOD 1000000007
  9. int maps[105][105];
  10. int main()
  11. {
  12.     int n,m,v,temp,ans,gg;
  13.     while(scanf("%d",&n),n)
  14.     {
  15.         ans=666666;
  16.         for(int i=1;i<=n;i++)
  17.         {
  18.             for(int j=1;j<=n;j++)
  19.             {
  20.                 if(i==j)
  21.                     maps[i][j]=0;
  22.                 else
  23.                     maps[i][j]=666666;
  24.             }
  25.             scanf("%d",&m);
  26.             while(m--)
  27.             {
  28.                 scanf("%d",&v);
  29.                 scanf("%d",maps[i]+v);
  30.             }
  31.         }
  32.         for(int k=1;k<=n;k++)
  33.             for(int i=1;i<=n;i++)
  34.                 for(int j=1;j<=n;j++)
  35.                     maps[i][j]=min(maps[i][j],maps[i][k]+maps[k][j]);
  36.         for(int i=1;i<=n;i++)
  37.         {
  38.             temp=0;
  39.             for(int j=1;j<=n;j++)
  40.                 temp=max(temp,maps[i][j]);
  41.             if(temp<ans)
  42.             {
  43.                 ans=temp;
  44.                 gg=i;
  45.             }
  46.         }
  47.         if(ans==666666)
  48.             printf("disjoint\n");
  49.         else
  50.             printf("%d %d\n",gg,ans);
  51.     }
  52.     return 0;
  53. }

D 昂贵的聘礼

题目大意：

    有N(1<=N<=100)个物品，第i个物品的价格为Pi，等级为Li。除了直接购买之外，还可以用指定的某个物品来抵消一部分从而降低价格，一个物品可能有多个可以降低它价格的物品，但是只能同一个目标物品的价格一次。同时，如果之前交易过的人和当前交易的人等级差超过M，当前的人将会拒绝交易。问你为了拿到1号物品，最少需要花多少钱。

解题思路：

    如果不考虑等级差不超过M的限制，那么这道题就是一道很简单的最短路的题。从0号点到i号点建一条权值为Pi的单向边，从每个指定物品到被他降低价格的物品建一条权值为降低后价格的单向边，以0号点为起点跑最短路，然后看到1号点的最短距离是多少。
    因为最后一定要买到1号物品，所以我们可以确定，一路上所有交易过的物品的等级区间满足以下两个条件：(1)最高等级和最低等级差距不超过M(2)L1属于这个区间。于是我们可以假设等级区间为[L1-M，L1]，[L1-M+1，L1+1]...[L1-1，L1+M-1]，[L1，L1+M]。枚举等级区间，只考虑等级在这个区间内的点，跑最短路，就可以得到这个等级区间对应的答案。所有区间的答案中的最小值就是最后的答案。
    时间复杂度o(M*k*N^2)，空间复杂度o(N^2)。

AC代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<queue>
  5. #define pq priority_queue
  6. #define Pi acos(-1.0)
  7. using namespace std;
  8. #define MOD 1000000007
  9. struct Edge
  10. {
  11.     int to,d;
  12. }edges[10105];
  13. int pre[10105];
  14. int p[105],l[105],dis[105],nums;
  15. int root[105];
  16. bool life[105];
  17. queue <int> q;
  18. int main()
  19. {
  20.     int ans,u,temp,now;
  21.     int n,m,x;
  22.     scanf("%d%d",&m,&n);
  23.     nums=0;
  24.     memset(root,0,sizeof(root));
  25.     memset(pre,0,sizeof(pre));
  26.     for(int i=1;i<=n;i++)
  27.     {
  28.         scanf("%d%d%d",p+i,l+i,&x);
  29.         while(x--)
  30.         {
  31.             nums++;
  32.             scanf("%d%d",&u,&edges[nums].d);
  33.             pre[nums]=root[u];
  34.             root[u]=nums;
  35.             edges[nums].to=i;
  36.         }
  37.     }
  38.     ans=p[1];
  39.     for(int i=1;i<=n;i++)
  40.     {
  41.         nums++;
  42.         pre[nums]=root[0];
  43.         root[0]=nums;
  44.         edges[nums].to=i;
  45.         edges[nums].d=p[i];
  46.     }
  47.     for(int flag=l[1]-m;flag<=l[1];flag++)
  48.     {
  49.         life[0]=1;
  50.         for(int i=1;i<=n;i++)
  51.             dis[i]=p[1]+1;
  52.         q.push(0);
  53.         while(!q.empty())
  54.         {
  55.             now=q.front();
  56.             q.pop();
  57.             life[now]=0;
  58.             temp=root[now];
  59.             while(temp)
  60.             {
  61.                 if(l[edges[temp].to]>=flag && l[edges[temp].to]<=flag+m)
  62.                 {
  63.                     if(dis[now]+edges[temp].d<dis[edges[temp].to])
  64.                     {
  65.                         dis[edges[temp].to]=dis[now]+edges[temp].d;
  66.                         if(!life[edges[temp].to])
  67.                         {
  68.                             life[edges[temp].to]=1;
  69.                             q.push(edges[temp].to);
  70.                         }
  71.                     }
  72.                 }
  73.                 temp=pre[temp];
  74.             }
  75.         }
  76.         ans=min(dis[1],ans);
  77.     }
  78.     printf("%d\n",ans);
  79.     return 0;
  80. }

E 最短路径问题

题目大意：

    有n(1<n<=1000)个点，m(1<m<=100000)条无向边，第i条边连接ai和bi，距离为d，花费为p。问从起点s到终点t的最小距离和这个距离下的最小花费为多少。
    多组数据。

解题思路：

    这题相当于就是用距离和花费两个属性来表示一条边的权值，只需要在松弛的判断操作那里进行一下小改动即可。
    时间复杂度o(k*m)，空间复杂度o(m)。

AC代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<queue>
  5. #define pq priority_queue
  6. #define Pi acos(-1.0)
  7. using namespace std;
  8. #define MOD 1000000007
  9. struct Edge
  10. {
  11.     int to,d,p;
  12. }edges[200005];
  13. int pre[200005];
  14. int p[1005],dis[1005];
  15. int root[1005];
  16. bool life[1005];
  17. queue <int> q;
  18. int main()
  19. {
  20.     int u,v,nowd,nowp;
  21.     int temp,now;
  22.     int n,m,s,t;
  23.     while(scanf("%d%d",&n,&m),n ||m)
  24.     {
  25.         memset(root,0,sizeof(root));
  26.         memset(pre,0,sizeof(pre));
  27.         for(int i=1;i<=n;i++)
  28.             dis[i]=1008600866;
  29.         for(int i=1;i<=m;i++)
  30.         {
  31.             scanf("%d%d%d%d",&u,&v,&nowd,&nowp);
  32.             pre[i]=root[u];
  33.             root[u]=i;
  34.             edges[i].to=v;
  35.             edges[i].d=nowd;
  36.             edges[i].p=nowp;
  37.             pre[i+m]=root[v];
  38.             root[v]=i+m;
  39.             edges[i+m].to=u;
  40.             edges[i+m].d=nowd;
  41.             edges[i+m].p=nowp;
  42.         }
  43.         scanf("%d%d",&s,&t);
  44.         life[s]=1;
  45.         p[s]=dis[s]=0;
  46.         q.push(s);
  47.         while(!q.empty())
  48.         {
  49.             now=q.front();
  50.             q.pop();
  51.             life[now]=0;
  52.             temp=root[now];
  53.             while(temp)
  54.             {
  55.                 if(dis[now]+edges[temp].d<dis[edges[temp].to] || (dis[now]+edges[temp].d==dis[edges[temp].to] && p[now]+edges[temp].p<p[edges[temp].to]))
  56.                 {
  57.                     dis[edges[temp].to]=dis[now]+edges[temp].d;
  58.                     p[edges[temp].to]=p[now]+edges[temp].p;
  59.                     if(!life[edges[temp].to])
  60.                     {
  61.                         life[edges[temp].to]=1;
  62.                         q.push(edges[temp].to);
  63.                     }
  64.                 }
  65.                 temp=pre[temp];
  66.             }
  67.         }
  68.         printf("%d %d\n",dis[t],p[t]);
  69.     }
  70.     return 0;
  71. }

F Choose the best route

题目大意：

    有n(n<1000)个公交车站点，有m(m<20000)条有向边，第i条边连接pi和qi，花费的时间为ti(0<ti<=1000)。有w(0<w<n)个站可以选择作为起点，终点为s，问能不能到达，能的话最少花多少时间。
    多组数据。

解题思路：

    进行枚举起点进行单源最短路在时间复杂度上是不可行的，我们可以把0号点和每个候选起点连上权值为0的边，这样起点就变为了1个，只需要跑一次单源最短路即可。
    小细节：在spfa算法中，只需要一开始把潜在起点都入队，就不需要引入0号点了。
    时间复杂度o(k*m)，空间复杂度o(m)。

AC代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<queue>
  5. #define pq priority_queue
  6. #define Pi acos(-1.0)
  7. using namespace std;
  8. #define MOD 1000000007
  9. struct Edge
  10. {
  11.     int to,d;
  12. }edges[20005];
  13. int pre[20005];
  14. int dis[1005];
  15. int root[1005];
  16. bool life[1005];
  17. queue <int> q;
  18. int main()
  19. {
  20.     int u,v,nowd;
  21.     int temp,now;
  22.     int n,m,s,x,w;
  23.     while(~scanf("%d%d%d",&n,&m,&s))
  24.     {
  25.         memset(root,0,sizeof(root));
  26.         memset(pre,0,sizeof(pre));
  27.         for(int i=1;i<=n;i++)
  28.             dis[i]=66666666;
  29.         for(int i=1;i<=m;i++)
  30.         {
  31.             scanf("%d%d%d",&u,&v,&nowd);
  32.             pre[i]=root[u];
  33.             root[u]=i;
  34.             edges[i].to=v;
  35.             edges[i].d=nowd;
  36.         }
  37.         scanf("%d",&w);
  38.         while(w--)
  39.         {
  40.             scanf("%d",&x);
  41.             life[x]=1;
  42.             dis[x]=0;
  43.             q.push(x);
  44.         }
  45.         while(!q.empty())
  46.         {
  47.             now=q.front();
  48.             q.pop();
  49.             life[now]=0;
  50.             temp=root[now];
  51.             while(temp)
  52.             {
  53.                 if(dis[now]+edges[temp].d<dis[edges[temp].to])
  54.                 {
  55.                     dis[edges[temp].to]=dis[now]+edges[temp].d;
  56.                     if(!life[edges[temp].to])
  57.                     {
  58.                         life[edges[temp].to]=1;
  59.                         q.push(edges[temp].to);
  60.                     }
  61.                 }
  62.                 temp=pre[temp];
  63.             }
  64.         }
  65.         if(dis[s]==66666666)
  66.             printf("-1\n");
  67.         else
  68.             printf("%d\n",dis[s]);
  69.     }
  70.     return 0;
  71. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注