- 技术博客
- 洛谷：P1629 邮递员送信（图，地杰斯特拉算法，普及提高- ）
题目：
分析：我想到了去的时候是digkstral算法。返回的时候难道是求n个地杰斯特拉算法？然后只用到了一半。
看题解，我真就是个菜鸡，返回的时候不就是反向建个边，然后，还是从起始点1点的地杰斯特拉算法吗？
代码：重写地杰斯特拉算法模板后再写吧！
#include<bits/stdc++.h>
using namespace std
;
struct node
{
int dis
;
int begin
;
int end
;
};
struct ppair
{
int dis
;
int pos
;
bool operator < (const ppair
& x
) const{
return x
.dis
<dis
;
}
};
priority_queue
<ppair
> q
;
priority_queue
<ppair
> q2
;
int m
,n
,n2
;
vector
<vector
<node
> > vvn
;
vector
<vector
<node
> > vvn2
;
int done
[1005];
int dis
[1005];
int done2
[1005];
int dis2
[1005];
void dijkstra_1()
{
dis
[1]=0;
q
.push( ( ppair
){0,1} );
while(!q
.empty())
{
ppair tem
=q
.top();
q
.pop();
if(done
[tem
.pos
]==1) continue;
done
[tem
.pos
]=1;
for(int i
=0;i
<vvn
[tem
.pos
].size();i
++)
{
if(dis
[vvn
[tem
.pos
][i
].end
]>dis
[vvn
[tem
.pos
][i
].begin
]+vvn
[tem
.pos
][i
].dis
)
{
dis
[vvn
[tem
.pos
][i
].end
]=dis
[vvn
[tem
.pos
][i
].begin
]+vvn
[tem
.pos
][i
].dis
;
q
.push( ( ppair
){dis
[vvn
[tem
.pos
][i
].end
],vvn
[tem
.pos
][i
].end
} );
}
}
}
}
void dijkstra_2()
{
dis2
[1]=0;
q2
.push( ( ppair
){0, 1} );
while(!q2
.empty())
{
ppair tem
=q2
.top();
q2
.pop();
if(done2
[tem
.pos
]==1) continue;
done2
[tem
.pos
]=1;
for(int i
=0;i
<vvn2
[tem
.pos
].size();i
++)
{
if(dis2
[vvn2
[tem
.pos
][i
].end
]>dis2
[vvn2
[tem
.pos
][i
].begin
]+vvn2
[tem
.pos
][i
].dis
)
{
dis2
[vvn2
[tem
.pos
][i
].end
]=dis2
[vvn2
[tem
.pos
][i
].begin
]+vvn2
[tem
.pos
][i
].dis
;
q2
.push( ( ppair
){dis2
[vvn2
[tem
.pos
][i
].end
],vvn2
[tem
.pos
][i
].end
} );
}
}
}
}
int main()
{
vector
<node
> vn
;
memset(done
,0,sizeof(done
));
cin
>>m
>>n
;
for(int i
=0;i
<=m
;i
++) vvn
.push_back(vn
);
for(int i
=0;i
<=m
;i
++) vvn2
.push_back(vn
);
for(int i
=0;i
<n
;i
++)
{
int a
,b
,c
;
cin
>>a
>>b
>>c
;
struct node nn
;
nn
.begin
=a
;
nn
.end
=b
;
nn
.dis
=c
;
vvn
[a
].push_back(nn
);
nn
.begin
=b
;
nn
.end
=a
;
vvn2
[b
].push_back(nn
);
}
for(int i
=0;i
<1005;i
++) dis
[i
]=(1<<30);
for(int i
=0;i
<1005;i
++) dis2
[i
]=(1<<30);
dijkstra_1();
memset(done2
,0,sizeof(done2
));
dijkstra_2();
long long ans
=0;
for(int i
=1;i
<=m
;i
++) ans
+=(dis
[i
]+dis2
[i
]);
cout
<<ans
;
}
