首页 > 代码库 > codevs3872 邮递员送信（SPFA）
codevs3872 邮递员送信（SPFA）
邮递员送信
时间限制: 1 Sec 内存限制: 64 MB
提交: 10 解决: 5
[提交][状态][讨论版]
题目描述
有一个邮递员要送东西，邮局在节点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,输入保证任意两点都能互相到达。
输出
输出仅一行，包含一个整数，为最少需要的时间。
样例输入
5 102 3 51 5 53 5 61 2 81 3 85 3 44 1 84 5 33 5 65 4 2样例输出
83提示
对于30%的数据，有1≤N≤200;
对于100%的数据，有1≤N≤1000,1≤M≤100000。
【分析】两次SPFA，第二次把边全反过来。
#include <iostream>#include <cstring>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <time.h>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#define inf 0x3f3f3f3f#define mod 1000000007typedef long long ll;using namespace std;const int N=1005;const int M=100005;int cost[N][N];ll d[N],D[N];int n,m;ll ans=0;bool vis[N];void spfa(int s) { int i,j,now; memset(vis,false,sizeof(vis)); for(i=1; i<=n; i++) { d[i]=inf; } d[s]=0; vis[s]=true; queue<int> q; q.push(s); while(!q.empty()) { now=q.front(); q.pop();vis[now]=false; for(i=1; i<=n; i++) { if(d[i]>d[now]+cost[now][i]) { d[i]=d[now]+cost[now][i]; if(!vis[i]) q.push(i),vis[i]=true; } } } for(int i=2; i<=n; i++)ans+=d[i];}int main() { int i,j,a,b,c; scanf("%d%d",&n,&m); for(i=1; i<=n; ++i) { for(j=1; j<=i; j++) { if(i==j) cost[i][j]=0; else cost[i][j]=cost[j][i]=inf; } } for(i=0; i<m; i++) { scanf("%d%d%d",&a,&b,&c); cost[a][b]=min(cost[a][b],c); } spfa(1); for(i=1; i<=n; ++i)for(j=i+1; j<=n; ++j)swap(cost[i][j],cost[j][i]); spfa(1); cout<<ans<<endl; return 0;}
codevs3872 邮递员送信（SPFA）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。