记录编号	565484	评测结果	AAAAAAAAAA
题目名称	旅游纪念	最终得分	100
用户昵称	该账号已注销	是否通过	通过
代码语言	C++	运行时间	0.514 s
提交时间	2021-10-20 19:55:16	内存使用	9.45 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
struct edge{
    int t,n,w;
}e[1000010];
int hd[N*4],cnt=0,n,m,d[N*4];
bool v[N*4]={0};
void add(int x,int y,int z)
{
    e[++cnt].t=y;
    e[cnt].n=hd[x];
    e[cnt].w=z;
    hd[x]=cnt;
    return ;
}
void spfa()
{
    memset(v,0,sizeof(v));
    memset(d,0x3f,sizeof(d));
    queue<int>q;
    q.push(1);
    v[1]=1;
    d[1]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        v[x]=0;
        for(int i=hd[x];i;i=e[i].n)
        {
            int y=e[i].t,z=e[i].w;
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(v[y]==0)
                {
                    v[y]=1;
                    q.push(y); 
                }
            }
        }
    }
}
int main(){
    freopen("keepsake.in","r",stdin);
    freopen("keepsake.out","w",stdout);
      cin>>n>>m;
      for(int i=1;i<=m;i++)
      {
          int x,y,z;
          cin>>x>>y>>z;
          add(x,y,z);
          add(x+n,y+n,z);
          add(x+n*2,y+n*2,z);
      }
      for(int i=1;i<=n;i++)
      {
          int p;
          cin>>p;
          add(i,i+n,p);
          add(i+n,i+n*2,-p);
      }
      spfa();
      cout<<d[n*3]<<endl;
      return 0;
}