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

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 ;

}