POJ 3013 Big Christmas Tree(SPFA)

题目地址:http://poj.org/problem?id=3013
来源:POJ

题意:有t组数据,有n个点,每个点的有一个权值,m条边.在保证所有的点都构成一个数的情况下,求cost[i]*sum[i]之和(cost[i]表示与这个点的父结点相连的边的权值,sum[i]表示这个点及这个点的孩子的权值之和). POJ 3013 Big Christmas Tree(SPFA)
即便是知道了最短路问题(刚开始应该会想成最小生成树),但是这个题还是有很多需要注意的地方.
1.dis是LL 类型的
2.n=0和n=1时,输出是0,但是要在边输出完以后再进行判断,n=1时,会出现1->1的边.如果在输入边之前就进行判断会RE
3.对于vector中的数据,每次输入都要进行清空

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

typedef long long LL;
const LL inf=0x3f3f3f3f3f3f3f3f;
const int Max_n=5e4+10;
LL w[Max_n],dis[Max_n];
bool vis[Max_n];

struct Edge{
    int u,cost;
    Edge(){}
    Edge(int u,int cost):u(u),cost(cost){}
};

vector<Edge>G[Max_n];
queue<int>q;

LL spfa(int n){
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;
    vis[1]=true;
    q.push(1);
    while(!q.empty()){
        int v=q.front();q.pop();vis[v]=false;
        for(unsigned int i=0;i<G[v].size();i++){
            Edge edge=G[v][i];
            if(dis[edge.u]>dis[v]+edge.cost){
                dis[edge.u]=dis[v]+edge.cost;
                if(!vis[edge.u]){
                    vis[edge.u]=true;
                    q.push(edge.u);
                }
            }
        }
    }
    LL ans=0;
    for(int i=1;i<=n;i++){
        ans+=w[i]*dis[i];
        if(dis[i]==inf)
            return -1;
    }
    return ans;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<=n;i++)
            scanf("%I64d",&w[i]);
        for(int i=1;i<=m;i++){
            int from,to,cost;
            scanf("%d%d%d",&from,&to,&cost);
            G[from].push_back(Edge(to,cost));
            G[to].push_back(Edge(from,cost));
        }
        if(n==0||n==1){
            printf("0\n");
            continue;
        }
        if(m==0){
            printf("No Answer\n");
            continue;
        }
        LL ans=spfa(n);
        if(ans==-1)
            printf("No Answer\n");
        else
            printf("%I64d\n",ans);
    }
    return 0;
}

POJ 3013 Big Christmas Tree(SPFA)

相关推荐