下面的程序实现了,使用优先队列的dijkstra算法求解起点为0 的单源最短路问题。有定义如下: typedef pair<int, int> pii; priority_queue<pii, vector<pii>, greater<pii> > q; pair在比较时会先比较第一个数,再比较第二个数,因此q是一个小元素优先的优先队列。对于图中节点x,first[x]代表其第一条出边的编号。对于图中编号为e的边,v[e]代表这条边的终点,w[e]代表这条边的权值。 试完善以下代码: bool done[MAXN]; for (int i = 0; i < n; i++) d[i] = (i == 0 ? 0 : INF); memset(done, false, sizeof(done)); q.push(make_pair(d[0], 0)); while(!q.empty()) {         pii u = q.top(); q.pop();         int x = u.second;         if (done[x])              ;         done[x] = true;         for (int e = first[x]; e != -1; e = next[e])           if (                       ) {              d[v[e]] =                ;                            ;           } }-笔试面试资料

这是qklbishe.com第16463 篇笔试面试资料
提供答案分析,通过本文《下面的程序实现了,使用优先队列的dijkstra算法求解起点为0 的单源最短路问题。有定义如下: typedef pair<int, int> pii; priority_queue<pii, vector<pii>, greater<pii> > q; pair在比较时会先比较第一个数,再比较第二个数,因此q是一个小元素优先的优先队列。对于图中节点x,first[x]代表其第一条出边的编号。对于图中编号为e的边,v[e]代表这条边的终点,w[e]代表这条边的权值。 试完善以下代码: bool done[MAXN]; for (int i = 0; i < n; i++) d[i] = (i == 0 ? 0 : INF); memset(done, false, sizeof(done)); q.push(make_pair(d[0], 0)); while(!q.empty()) {         pii u = q.top(); q.pop();         int x = u.second;         if (done[x])              ;         done[x] = true;         for (int e = first[x]; e != -1; e = next[e])           if (                       ) {              d[v[e]] =                ;                            ;           } }-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

下面的程序实现了,使用优先队列的dijkstra算法求解起点为0的单源最短路问题。有定义如下:

typedef pair<int, int> pii;

priority_queue<pii, vector<pii>, greater<pii> > q;

pair在比较时会先比较第一个数,再比较第二个数,因此q是一个小元素优先的优先队列。对于图中节点x,first[x]代表其第一条出边的编号。对于图中编号为e的边,v[e]代表这条边的终点,w[e]代表这条边的权值。

试完善以下代码:

bool done[MAXN];

for (int i = 0; i < n; i++) d[i] = (i == 0 ? 0 : INF);

memset(done, false, sizeof(done));

q.push(make_pair(d[0], 0));

while(!q.empty()) {

        pii u = q.top(); q.pop();

        int x = u.second;

        if (done[x])              ;

        done[x] = true;

        for (int e = first[x]; e != -1; e = next[e])

          if (                       ) {

             d[v[e]] =                
                          ;

          }

}

下面的程序实现了,使用优先队列的dijkstra算法求解起点为0 的单源最短路问题。有定义如下:    typedef pair&lt;int, int&gt; pii;    priority_queue&lt;pii, vector&lt;pii&gt;, greater&lt;pii&gt; &gt; q;    pair在比较时会先比较第一个数,再比较第二个数,因此q是一个小元素优先的优先队列。对于图中节点x,first[x]代表其第一条出边的编号。对于图中编号为e的边,v[e]代表这条边的终点,w[e]代表这条边的权值。    试完善以下代码:    bool done[MAXN];    for (int i = 0; i &lt; n; i++) d[i] = (i == 0 ? 0 : INF);    memset(done, false, sizeof(done));    q.push(make_pair(d[0], 0));    while(!q.empty()) {            pii u = q.top(); q.pop();            int x = u.second;            if (done[x])              ;            done[x] = true;            for (int e = first[x]; e != -1; e = next[e])              if (                       ) {                 d[v[e]] =                ;                               ;              }    } 区块链毕设学生556781672号
continue;
d[x]+w[e]<d[v[e]];
d[v[e]]=d[x]+w[e]
q.push(make_pair(d[v[e]],v[e]));

2021-09-21 20:46:43 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 下面的程序实现了,使用优先队列的dijkstra算法求解起点为0 的单源最短路问题。有定义如下: typedef pair<int, int> pii; priority_queue<pii, vector<pii>, greater<pii> > q; pair在比较时会先比较第一个数,再比较第二个数,因此q是一个小元素优先的优先队列。对于图中节点x,first[x]代表其第一条出边的编号。对于图中编号为e的边,v[e]代表这条边的终点,w[e]代表这条边的权值。 试完善以下代码: bool done[MAXN]; for (int i = 0; i < n; i++) d[i] = (i == 0 ? 0 : INF); memset(done, false, sizeof(done)); q.push(make_pair(d[0], 0)); while(!q.empty()) {         pii u = q.top(); q.pop();         int x = u.second;         if (done[x])              ;         done[x] = true;         for (int e = first[x]; e != -1; e = next[e])           if (                       ) {              d[v[e]] =                ;                            ;           } }-笔试面试资料

提供最优质的资源集合

立即查看 了解详情