邮递员送信
题目描述
有一个邮递员要送东西,邮局在节点 \(1\)。他总共要送 \(n-1\) 样东西,其目的地分别是节点 \(2\) 到节点 \(n\)。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 \(m\) 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 \(n-1\) 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数,\(n\) 和 \(m\),表示城市的节点数量和道路数量。
第二行到第 \((m+1)\) 行,每行三个整数,\(u,v,w\),表示从 \(u\) 到 \(v\) 有一条通过时间为 \(w\) 的道路。
输出格式
输出仅一行,包含一个整数,为最少需要的时间。
样例 #1
样例输入 #1
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2
样例输出 #1
83
提示
对于 \(30\%\) 的数据,\(1 \leq n \leq 200\)。
对于 \(100\%\) 的数据,\(1 \leq n \leq 10^3\),\(1 \leq m \leq 10^5\),\(1\leq u,v \leq n\),\(1 \leq w \leq 10^4\),输入保证任意两点都能互相到达。
思路
迪杰斯特拉模板题,注意题目中的边为单向边,解决问题可以正反向建边。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int v,w;
};
priority_queue<pair<int,int>> q;
priority_queue<pair<int,int>> qq;
int n,m;
vector<node> p[N];
vector<node> pp[N];
int ans;
int d[N],vis[N],pre[N];
int d1[N],vis1[N],pre1[N];
void dijisk(int s)
{
for(int i=0;i<=n;i++) d[i]=0x3f3f3f3f;
d[s]=0;
q.push({0,s});
while(q.size())
{
auto t=q.top();
q.pop();
int u=t.second;
if(vis[u]) continue;
vis[u]=1;
for(auto it:p[u])
{
int v=it.v;
int w=it.w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
pre[v]=u;
q.push({-d[v],v});
}
}
}
}
void dijisk1(int s)
{
for(int i=0;i<=n;i++) d1[i]=0x3f3f3f3f;
d1[s]=0;
qq.push({0,s});
while(qq.size())
{
auto t=qq.top();
qq.pop();
int u=t.second;
if(vis1[u]) continue;
vis1[u]=1;
for(auto it:pp[u])
{
int v=it.v;
int w=it.w;
if(d1[v]>d1[u]+w)
{
d1[v]=d1[u]+w;
pre1[v]=u;
qq.push({-d1[v],v});
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
p[a].push_back({b,c});
pp[b].push_back({a,c});
}
dijisk(1);
dijisk1(1);
for(int i=1;i<=n;i++) ans+=d[i];
for(int i=1;i<=n;i++) ans+=d1[i];
cout<<ans;
return 0;
}```
标签:10,图论,int,leq,邮递员,push,P1629,d1
From: https://www.cnblogs.com/marshuo/p/18153280