华师一附中OI组

标题: 最短路径 讨论 [打印本页]
作者: admin    时间: 2018-4-14 20:39
标题: 最短路径 讨论
给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。输出一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）
【思路】典型的做法是dijistra，这个我们用邻接表来存图，邻接矩阵虽然直观确实太占空间了。
  1. #include<iostream>
  2. using namespace std;
  3. const int inf=2147483647;
  4. const int mm=500050;
  5. const int mn=10010;
  6. int n,m,s;
  7. int nxt[mm],ev[mm],ew[mm];
  8. int dist[mn],vist[mn],nbs[mn],p[mn];

  10. int getmin()
  11. {
  12.     int m,k,i;
  13.     m=inf;
  14.     k=0;  ///起点，无路可找的时候就返回0
  15.     ///for (i=1;i<=n;i++)  cout<<dist[i]<<' '; cout<<endl;
  16.     for (i=1; i<=n; i++)
  17.         if (!vist[i])
  18.             if (dist[i]<m)
  19.             {
  20.                 m=dist[i];
  21.                 k=i;
  22.             }
  23.     return k;
  24. }

  26. void dijkstra(int src)
  27. {
  28.     int i,j,u,v;
  29.     for(i=1; i<=n; i++)
  30.     {
  31.         dist[i]=inf;
  32.         vist[i]=0;
  33.     };
  34.     dist[src]=0;
  35.     while(1)  ///因为是找所有的路，所以这个和标准写法有点不一样
  36.     {
  37.         u=getmin();
  38.         if (u==0) return ;  ///靠这句话终结程序
  39.         vist[u]=1;
  40.         for(j=nbs[u]; j!=0; j=nxt[j])
  41.         {
  42.             v=ev[j];
  43.             if(!vist[v]&&dist[u]+ew[j]<dist[v])
  44.             {
  45.                 dist[v]=dist[u]+ew[j];
  46.                 p[v]=u;
  47.             }
  48.         }
  49.     }
  50. }
  51. void printpath(int i)///反推路径找到S到I的路
  52. {
  53.     int path[mn]={i,}; ///初始终点
  54.     int j=0,k=i;
  55.     while (p[k]!=0)  ///完全类似导弹飞机的倒推
  56.     {
  57.         j++;
  58.         path[j]=p[k];
  59.         k=p[k];
  60.     }
  61.     cout<<s<<"-->"<<i<<':';
  62.     for (; j>=0; j--) cout<<path[j];
  63.     cout<<endl;
  64. }
  65. int main()
  66. {
  67.     int i,u,v,w;
  68.     cin>>n>>m>>s;
  69.     for(i=1; i<=n; i++)nbs[i]=0;
  70.     for(i=1; i<=m; i++)
  71.     {
  72.         cin>>u>>v>>w;
  73.         nxt[i]=nbs[u];
  74.         nbs[u]=i;
  75.         ev[i]=v;
  76.         ew[i]=w;///这里考虑一下如何去掉重复的边，
  77.     }
  78.     dijkstra(s);
  79.     for (i=1; i<=n; i++)  cout<<dist[i]<<' ';
  80.     ///cout<<endl;
  81.     ///for (i=1; i<=n; i++)  printpath(i);
  82.     return 0;
  83. }

复制代码



作者: admin    时间: 2018-4-14 20:39
这个程序对于一般的数据基本可以得到正确解，但是每次getmin确实会浪费不少的时间，快捷的做法我们就是用一个优先队列来存放dist[1..n]，不要getmin函数，每次进循环的时候 u=pq.top();pq.pop(); 每次改了dist[v]后加上pq.push(v);当然，前面不要忘记：
struct cmp
{
    bool operator()(int &a, int &b) const
    {
        //因为优先出列判定为!cmp，所以反向定义实现最小值优先
        return dist[a] > dist[b];
    }
};

priority_queue<int, vector<int>, cmp> pq;  ///定义优先队列  注意比较方式
作者: admin    时间: 2018-4-15 21:12
P3371 【模板】单源最短路径  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35866
P1339 [USACO09OCT]热浪Heat Wave  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36361
P1576 最小花费  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36362
P1629 邮递员送信  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36363
P1744 采购特价商品  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36364
P2176 [USACO14FEB]路障Roadblock  http://www.hsyit.cn/forum.php?mod=viewthread&tid=3718
P1186 玛丽卡  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36365



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2