最短路径 讨论

admin

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入第一行包含三个整数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];
   
9. 
   
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. }
    
25. 
    
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. }
    
84. 
    

复制代码

admin

这个程序对于一般的数据基本可以得到正确解，但是每次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

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