邮递员送信（letter）

2024-02-05 10:58

文章标签 邮递员送信 letter

本文主要是介绍邮递员送信（letter），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

By Stockholm

邮递员送信（letter）

题目描述有一个邮递员要送东西，邮局在节点 1.他总共要送 N-1 样东西，其目的地分别是 2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 M 条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这 N-1 样东西并且最终回到邮局
最少需要多少时间。
输入输出格式
输入格式：
第一行包括两个整数 N 和 M。
第 2 到第 M+1 行，每行三个数字 U、V、W，表示从 A 到 B 有一条
需要 W 时间的道路。满足 1<=U,V<=N,1<=W<=10000,输入保
证任意两点都能互相到达。
【数据规模】
对于 30%的数据，有 1≤N≤200;
对于 100%的数据，有 1≤N≤1000,1≤M≤100000。
输出格式：
输出仅一行，包含一个整数，为最少需要的时间。输入输出样例
输入样例#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
这个题明显的显现出了 SPFA 这个方法的优势。一个双向SPFA完美AC。

代码（C++）

#include<iostream>
#include<cstdio>
#include<cstdlib>#include<cstring>
#include<deque>
using namespace std;
int i,j,m,n;
int head[1001],hed2[1001];
int us[1001];
int dis[1001];
long long ans;
struct node
{
int yy;
int v;
struct node *nxt;
}a[400005],e[400005];
int r()
{
int aans=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();while(ch>='0'&&ch<='9')
{
aans*=10;
aans+=ch-'0';
ch=getchar();
}
return aans;
}
int spfa1(int x)
{
us[x]=1;
deque<int>q;
dis[x]=0;
q.push_front(x);
struct node *p;
while(!q.empty())
{
x=q.front();
p=&a[head[x]];
us[x]=0;
q.pop_front();while(p->yy!=0)
{
if(dis[x]+p->v<dis[p->yy])
{
dis[p->yy]=dis[x]+p->v;
if(!us[p->yy])
{
if(q.empty()||dis[q.front()]>dis[p->yy])
q.push_front(p->yy);
else
q.push_back(p->yy);
us[p->yy]=1;
}
}
p=p->nxt;
}
}
}int spfa2(int x)
{
us[x]=1;
deque<int>q;
dis[x]=0;
q.push_front(x);
struct node *p;
while(!q.empty())
{
x=q.front();
p=&e[hed2[x]];
us[x]=0;
q.pop_front();
while(p->yy!=0)
{
if(dis[x]+p->v<dis[p->yy])
{
dis[p->yy]=dis[x]+p->v;
if(!us[p->yy])
{if(q.empty()||dis[q.front()]>dis[p->yy])
q.push_front(p->yy);
else
q.push_back(p->yy);
us[p->yy]=1;
}
}
p=p->nxt;
}
}
}
int main()
{
n=r(),m=r();
int x,y,z;
for(i=1;i<=m;i++)
{
x=r(),y=r(),z=r();
a[i].yy=y,a[i].v=z;
a[i].nxt=&a[head[x]];head[x]=i;
e[i].yy=x,e[i].v=z;
e[i].nxt=&e[hed2[y]];
hed2[y]=i;
}
memset(dis,0x7f7f7f7f,sizeof(dis));
spfa1(1);
for(i=1;i<=n;i++)
ans+=dis[i];
memset(dis,0x7f7f7f7f,sizeof(dis));
spfa2(1);
for(i=1;i<=n;i++)
ans+=dis[i];
cout<<ans;
return 0;
}