邮递员送信
时间限制: 1 Sec 内存限制: 64 MB
提交: 10 解决: 5
[提交][状态][讨论版]
题目描述
有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条
道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。
道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这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=;
const int M=;
int cost[N][N];
ll d[N],D[N];
int n,m;
ll ans=;
bool vis[N];
void spfa(int s) {
int i,j,now;
memset(vis,false,sizeof(vis));
for(i=; i<=n; i++) {
d[i]=inf;
}
d[s]=;
vis[s]=true;
queue<int> q;
q.push(s);
while(!q.empty()) {
now=q.front();
q.pop();vis[now]=false;
for(i=; 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=; i<=n; i++)ans+=d[i];
}
int main() {
int i,j,a,b,c;
scanf("%d%d",&n,&m);
for(i=; i<=n; ++i) {
for(j=; j<=i; j++) {
if(i==j) cost[i][j]=;
else cost[i][j]=cost[j][i]=inf;
}
}
for(i=; i<m; i++) {
scanf("%d%d%d",&a,&b,&c);
cost[a][b]=min(cost[a][b],c);
}
spfa();
for(i=; i<=n; ++i)for(j=i+; j<=n; ++j)swap(cost[i][j],cost[j][i]);
spfa();
cout<<ans<<endl;
return ;
}