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 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

样例输出

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 1000000007 typedef 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; } View Code

转载于:https://www.cnblogs.com/jianrenfang/p/5827279.html

总结

以上是生活随笔为你收集整理的codevs3872 邮递员送信（SPFA）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。