[关闭]
@iamtts 2017-02-25T12:07:59.000000Z 字数 4434 阅读 749

寒假第九次训练-最短路

A - 最短路

题目大意：给n个路口，m条路，走每条路花费不等的时间，求从1号路口到n号路口的最短时间

解题思路：裸dijkstra

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. #include <stack>
  9. #include <queue>
  10. #include <cmath>
  11. #include <sstream>
  12. using namespace std;
  13. #define MAXN 200+10
  14. #define INF 1<<20
  16. int m,n;
  17. int d[105][105],cost[105];
  18. void dijkstra(int s)
  19. {
  20.     int v=-1;
  21.     bool used[105];
  22.     memset(used,0,sizeof(used));
  23.     cost[s]=0;
  24.     while (true)
  25.     {
  26.         v=-1;
  27.         for (int u=1;u<=n;u++)
  28.             if (!used[u] && (v==-1 || cost[v]>cost[u])) v=u;
  29.         if (v==-1) break;
  30.         used[v]=true;
  31.         for (int u=1;u<=n;u++)
  32.             if (d[v][u]>=0) cost[u]=min(cost[u],cost[v]+d[v][u]);
  34.     }
  35. }
  36. int main()
  37. {
  38.     while (scanf("%d%d",&n,&m),m+n)
  39.     {
  40.         memset(d,-1,sizeof(d));
  41.         fill(cost,cost+105,INF);
  42.         while (m--)
  43.         {
  44.             int u,v,dis;
  45.             scanf("%d%d%d",&u,&v,&dis);
  46.             d[u][v]=dis;
  47.             d[v][u]=dis;
  48.         }
  49.         dijkstra(1);
  50.         printf("%d\n",cost[n]);
  51.     }
  52.     return 0;
  53. }

B - Wormholes

题目大意：给定一个图，图上带正权的边无向，带负权的边有向，从1点出发，求是否存在路径使得最终返回1点且耗费时间小于0

解题思路：用bellman-ford算法，又因为可能存在负圈，所以一旦回到1点且耗费时间小于0就退出

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. #include <stack>
  9. #include <queue>
  10. #include <cmath>
  11. #include <sstream>
  12. using namespace std;
  13. #define MAXN 200+10
  14. #define INF 1<<20
  16. struct edge{int from,to,cost;};
  17. edge es[10000];
  18. int m,n,w,e;
  19. int d[600];
  20. void ford(int s)
  21. {
  22.     bool flag;
  23.     d[s]=0;
  24.     while (true)
  25.     {
  26.         flag=false;
  27.         for (int i=0;i<e;i++)
  28.         {
  29.             edge temp=es[i];
  30.             if (d[temp.from]!=INF && d[temp.to]>d[temp.from]+temp.cost) {d[temp.to]=d[temp.from]+temp.cost;flag=true;}
  31.             if (d[1]<0) return;
  32.         }
  33.         if (!flag) return;
  34.     }
  35. }
  36. int main()
  37. {
  38.     int F;
  39.     scanf("%d",&F);
  40.     while (F--)
  41.     {
  42.         fill(d,d+600,INF);
  43.         scanf("%d%d%d",&n,&m,&w);
  44.         e=0;
  45.         while (m--)
  46.         {
  47.             int u,v,dis;
  48.             scanf("%d%d%d",&u,&v,&dis);
  49.             es[e].from=u;es[e].to=v;es[e].cost=dis;
  50.             e++;
  51.             es[e].from=v;es[e].to=u;es[e].cost=dis;
  52.             e++;
  53.         }
  54.         while (w--)
  55.         {
  56.             int u,v,dis;
  57.             scanf("%d%d%d",&u,&v,&dis);
  58.             es[e].from=u;es[e].to=v;es[e].cost=-dis;
  59.             e++;
  60.         }
  61.         ford(1);
  62.         printf("%s\n",d[1]<0?"YES":"NO");
  63.     }
  64.     return 0;
  65. }

C - Stockbroker Grapevine

题目大意：给定n个人，每个人可以和pi个说话，说话消耗数量不等的时间，求将消息传给所有人耗费的最短时间

解题思路：用n次dijkstra算法，尝试从不同起点出发的最短时间

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. #include <stack>
  9. #include <queue>
  10. #include <cmath>
  11. #include <sstream>
  12. using namespace std;
  13. #define MAXN 200+10
  14. #define INF 1<<20
  16. int n;
  17. int d[105],cost[105][105];
  18. int dijkstra(int s)
  19. {
  20.     bool used[105];
  21.     int v,mx=-1;
  22.     memset(used,0,sizeof(used));
  23.     fill(d,d+105,INF);
  24.     d[s]=0;
  25.     while (true)
  26.     {
  27.         v=-1;
  28.         for (int u=1; u<=n; u++)
  29.             if (!used[u] && (v==-1 || d[v]>d[u])) v=u;
  30.         if (v==-1) break;
  31.         used[v]=true;
  32.         for (int u=1; u<=n; u++)
  33.         {
  34.             if (d[u]>d[v]+cost[v][u])
  35.             {
  36.                 d[u]=d[v]+cost[v][u];
  37.                 mx=max(mx,d[u]);
  38.                 //printf("%d\n",mx);
  39.             }
  40.         }
  41.     }
  42.     return mx;
  43. }
  44. int main()
  45. {
  46.     bool iszero[105];
  47.     while (scanf("%d",&n),n)
  48.     {
  49.         fill(iszero,iszero+105,0);
  50.         for (int i=0; i<105; i++)
  51.             for (int j=0; j<105; j++)
  52.                 cost[i][j]=INF;
  53.         for (int v=1; v<=n; v++)
  54.         {
  55.             int num;
  56.             scanf("%d",&num);
  57.             if (!num) iszero[v]=true;
  58.             while (num--)
  59.             {
  60.                 int u,t;
  61.                 scanf("%d%d",&u,&t);
  62.                 cost[v][u]=t;
  63.             }
  64.         }
  65.         pair<int,int> rec;
  66.         rec.second=INF;
  67.         for (int v=1; v<=n; v++)
  68.         {
  69.             if (iszero[v]) continue;
  70.             else
  71.             {
  72.                 int val=dijkstra(v);
  73.                 bool flag=true;
  74.                 for (int i=1;i<=n;i++) if (d[i]==INF) flag=false;
  75.                 if (rec.second>val && flag)
  76.                     rec=make_pair(v,val);
  77.             }
  78.         }
  79.         if (rec.second==INF) printf("disjoint\n");
  80.         else printf("%d %d\n",rec.first,rec.second);
  81.     }
  83.     return 0;
  84. }

D - 昂贵的聘礼

题目大意：你要从酋长手中迎娶他的女儿，需要支付n金币的彩礼，这个部落所有人卖东西都有本身的价格和如果提供替代品的优惠价格，但是每个人有自身等级，如果曾经交易的人与目前交易的人等级差超过m级就无法交易，求花费最少金币数

解题思路：将所有人的等级按编号存起来，然后从最低的等级（保证可以交易到酋长）交易到最高的等级（同上），注意每次设置上限，即本次最低等级加上m。以酋长为终点，dijkstra循环尝试源点，取最小值。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. #include <stack>
  9. #include <queue>
  10. #include <cmath>
  11. #include <sstream>
  12. using namespace std;
  13. #define MAXN 200+10
  14. #define INF 1<<20
  16. int n,m;
  17. int d[105],cost[105][105],rank_[105],max_rank=-1;
  18. int dijkstra(int s,int l)
  19. {
  20.     bool used[105];
  21.     int v;
  22.     memset(used,0,sizeof(used));
  23.     fill(d,d+105,INF);
  24.     d[s]=cost[s][s];
  25.     while (true)
  26.     {
  27.         v=-1;
  28.         for (int u=1; u<=n; u++)
  29.             if (!used[u] && (v==-1 || d[v]>d[u]) && rank_[u]>=max_rank-m+l && rank_[u]<=max_rank+l) v=u;
  30.         if (v==-1) break;
  31.         used[v]=true;
  32.         for (int u=1; u<=n; u++)
  33.         {
  34.             if (rank_[u]>=max_rank-m+l && rank_[u]<=max_rank+l && d[u]==INF) d[u]=cost[u][u];
  35.             if (rank_[u]>=max_rank-m+l && rank_[u]<=max_rank+l && d[u]>d[v]+cost[v][u])
  36.             {
  37.                 d[u]=d[v]+cost[v][u];
  38.                 //printf("%d-%d:%d\n",v,u,d[u]);
  39.             }
  40.         }
  41.     }
  42. }
  43. int main()
  44. {
  45.     for (int i=0; i<105; i++)
  46.         for (int j=0; j<105; j++)
  47.             cost[i][j]=INF;
  49.     scanf("%d%d",&m,&n);
  51.     for (int i=1; i<=n; i++)
  52.     {
  53.         int money,rk,num;
  54.         scanf("%d%d%d",&money,&rk,&num);
  55.         cost[i][i]=money;
  56.         rank_[i]=rk;
  57.         if (i==1) max_rank=rk;
  58.         while (num--)
  59.         {
  60.             int no,mon;
  61.             scanf("%d%d",&no,&mon);
  62.             cost[no][i]=mon;
  63.         }
  64.     }
  65.     int ans=INF;
  66.     for (int l=0; l<=m; l++)
  67.     {
  68.         for (int i=1; i<=n; i++)
  69.         {
  70.             if (rank_[i]==max_rank-m+l)
  71.             {
  72.                 dijkstra(i,l);
  73.                 ans=min(ans,d[1]);
  74.             }
  75.         }
  76.     }
  77.     printf("%d\n",ans);
  78.     return 0;
  79. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注