烽火台（SDNU1030）（SPFA）

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;

#define inf 0x3f3f3f3f
using namespace std;

const int M=10005;

struct sss
{
    ll v; //终点
    ll w; //边的权值
    ll next;
}a[10005];

ll head[M]; //head存储的是以i为起点，最后输入的那个编号

ll vis[M],ven[M],nums[M]; //SPFS数组，vis记录最短路，ven记录是否在队列，nums记录入队次数
ll cnt=0; //链式前向星数组

void add(ll u,ll v,ll w)//链式前向星，加入节点
{
    a[cnt].v=v;
    a[cnt].w=w;
    a[cnt].next=head[u];
    head[u]=cnt++;
}


bool SPFA(int s,ll n)   //从s点开始出发，一共n条边
{
    queue <ll> q;
    vis[s]=0; //初始化距离
    ven[s]=1; //标记s在队列里面
    nums[s]++;//队列次数+1
    q.push(s);
    while(!q.empty())
    {
        ll x=q.front(); //以x点为翘板
        q.pop();   //出队
        ven[x]=0;  //标记不在队列
        for(ll i=head[x]; i>=0; i=a[i].next) //遍历与x节点连通的点
        {
            ll y=a[i].v;                //y是这条边的终点，以x为翘板，看初始点距离y点的距离可不可以更新
            if(vis[y] > vis[x] + a[i].w) //如果 初始点距离终点的距离 > （初始点距离x的距离+i这条边的权值） ——> 更新
            {
                vis[y] = vis[x] + a[i].w;
                if(ven[y]==0) //由于更新了节点，所以后续以这个为基础的最短路，也要更新下，所以如果在队列就不用加入，不在的话加入更新后续节点
                {
                    q.push(y);
                    ven[y]=1;//标记这个节点在队列中
                    nums[y]++;//记录加入次数
                    if(nums[y]>n) return false; //如果这个点加入超过n次，说明存在负圈，直接返回
                }
            }
        }
    }
    return true;
}
ll value[1005];
void init()
{
    cnt=0;
    memset(vis,inf,sizeof(vis));  //设s点到其余各个点的距离都是最大值
    memset(head,-1,sizeof(head));   //链式向前星里面的head数组初始化为-1
    memset(nums,0,sizeof(nums));
}
int main()
{
    ll n,m;
    while(cin >> m >> n) //m为初始的点的个数,n为边数
    {
        init();
        for (ll i=1;i<=m;i++)
        {
            cin >> value[i];
        }
        for(ll i=0;i<n;i++)
        {
            ll x,y,k;
            cin >> x >> y >> k;
            add(x, y, k);
            add(y, x, k);  //添加双向边
        }
        ll ans=0;
         /*以哪个点为初始点、一共有多少条边*/
        bool flag=SPFA(1,n);

        for (ll i=2;i<=m;i++)
        {
            if(vis[i]>=inf)
            {
                flag=false;
                break;
            }
            ans=ans+vis[i]*value[i];
        }
        if(flag) cout << ans << endl;
        else cout << "No Answer" << endl;
    }
    return 0;
}

//（把ven数组删掉了，直接用nums数组储存）
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;

#define inf 0x3f3f3f3f
using namespace std;

const int M=10005;

struct sss
{
    ll v; //终点
    ll w; //边的权值
    ll next;
}a[10005];

ll head[M]; //head存储的是以i为起点，最后输入的那个编号

ll vis[M],nums[M]; //SPFS数组，vis记录最短路，ven记录是否在队列，nums记录入队次数
ll cnt=0; //链式前向星数组

void add(ll u,ll v,ll w)//链式前向星，加入节点
{
    a[cnt].v=v;
    a[cnt].w=w;
    a[cnt].next=head[u];
    head[u]=cnt++;
}


bool SPFA(int s,ll n)   //从s点开始出发，一共n条边
{
    queue <ll> q;
    vis[s]=0; //初始化距离
    nums[s]++;//队列次数+1
    q.push(s);
    while(!q.empty())
    {
        ll x=q.front(); //以x点为翘板
        q.pop();   //出队
        nums[x]=0;  //标记不在队列
        for(ll i=head[x]; i>=0; i=a[i].next) //遍历与x节点连通的点
        {
            ll y=a[i].v;                //y是这条边的终点，以x为翘板，看初始点距离y点的距离可不可以更新
            if(vis[y] > vis[x] + a[i].w) //如果 初始点距离终点的距离 > （初始点距离x的距离+i这条边的权值） ——> 更新
            {
                vis[y] = vis[x] + a[i].w;
                if(nums[y]==0) //由于更新了节点，所以后续以这个为基础的最短路，也要更新下，所以如果在队列就不用加入，不在的话加入更新后续节点
                {
                    q.push(y);
                    nums[y]++;//记录加入次数
                    if(nums[y]>n) return false; //如果这个点加入超过n次，说明存在负圈，直接返回
                }
            }
        }
    }
    return true;
}
ll value[1005];
void init()
{
    cnt=0;
    memset(vis,inf,sizeof(vis));  //设s点到其余各个点的距离都是最大值
    memset(head,-1,sizeof(head));   //链式向前星里面的head数组初始化为-1
    memset(nums,0,sizeof(nums));
}
int main()
{
    ll n,m;
    while(cin >> m >> n) //m为初始的点的个数,n为边数
    {
        init();
        for (ll i=1;i<=m;i++)
        {
            cin >> value[i];
        }
        for(ll i=0;i<n;i++)
        {
            ll x,y,k;
            cin >> x >> y >> k;
            add(x, y, k);
            add(y, x, k);  //添加双向边
        }
        ll ans=0;
        /*以哪个点为初始点、一共有多少条边*/
        bool flag=SPFA(1,n);

        for (ll i=2;i<=m;i++)
        {
            if(vis[i]>=inf)
            {
                flag=false;
                break;
            }
            ans=ans+vis[i]*value[i];
        }
        if(flag) cout << ans << endl;
        else cout << "No Answer" << endl;
    }
    return 0;
}