T3 最短路 line

【问题描述】

给定一个 n 个点,m 条边的有向图,每个点有一个权值 a[i],表示这个点要到达多少次,1 为起始点,从 1 到 i 的距离为 d[i],请你输出∑a[i]*d[i],如果图不连通请输出“No Answer”。

【输入格式】

第一行为 n,m,含义见描述
接下来一行包含 n 个数,即 a[i]
接下来 m 行,每行三个数表示一条边的起点,终点,以及权值

【输出格式】

No Answer 或者一个数字

【样例输入】

3 2

1 1 2

1 2 15

2 3 1

【样例输出】

【数据说明】
n<=50000,m<=100000
∑w[i]、∑c[i]不超过 maxlongint ,可能存在重边

Solution

最短路板子题,算出1到每个点的最短路d[i]×a[i]

Code

// <line.cpp> - Thu Oct  6 08:17:54 2016

// This file is made by YJinpeng，created by XuYike's black technology automatically.

// Copyright (C) 2016 ChangJun High School, Inc.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <queue>

#define MOD 1000000007

#define INF 1e9

#define IN inline

#define RG register

using namespace std;

typedef long long LL;

typedef long double LB;

const int MAXN=;

const int MAXM=;

inline int max(int &x,int &y) {return x>y?x:y;}

inline int min(int &x,int &y) {return x<y?x:y;}

inline int gi() {

    register int w=,q=;register char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-')q=,ch=getchar();

    while(ch>=''&&ch<='')w=w*+ch-'',ch=getchar();

    return q?-w:w;

}

struct Dijskra{

    static const int N=,M=;

    int n,m,t;int d[N],fr[N],a[N];int to[M],ne[M],W[M];bool u[N];

    struct node{

        int s,p;

        bool operator<(node a)const{return s>a.s;}

    };

    priority_queue<node>q;

    void link(int u,int v,int w){

        to[++t]=v;ne[t]=fr[u];fr[u]=t;W[t]=w;

    }

    void read(){

        n=gi(),m=gi();

        for(int i=;i<=n;i++)a[i]=gi();

        while(m--){

            int u=gi(),v=gi(),w=gi();

            link(u,v,w);

        }

    }

    void Dij(int begin){

        for(int i=;i<=n;i++)d[i]=INF;

        q.push((node){d[begin]=,begin});memset(u,,sizeof(u));

        while(!q.empty()){

            while(u[q.top().p]&&!q.empty())q.pop();

            if(q.empty())break;

            int x=q.top().p;q.pop();u[x]=;

            for(int o=fr[x],y;y=to[o],o;o=ne[o])

                if(d[x]+W[o]<d[y]){

                    d[y]=d[x]+W[o];

                    q.push((node){d[y],y});

                }

        }

        for(int i=;i<=n;i++)

            if(d[i]==INF){printf("No Answer");exit();}

        LL ans=;

        for(int i=;i<=n;i++)ans+=1LL*d[i]*a[i];

        printf("%lld",ans);

    }

}e;

int main()

{

    freopen("line.in","r",stdin);

    freopen("line.out","w",stdout);

    e.read();e.Dij();

    return ;

}

巴特西

T3 最短路 line

T3 最短路 line

Solution

最新文章

热门文章