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