记录编号	565477	评测结果	AAAAAAAAAA
题目名称	旅游纪念	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.219 s
提交时间	2021-10-20 19:50:46	内存使用	6.37 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=50000+5;
const int M=100000+5;
struct sdf{
    int to,next,w;
}eg[5*M];
int head[3*N]={0},ne=0;
int n,m;
int d[3*N];
bool vis[3*N]={0};
void add(int x,int y,int z){
    eg[++ne]={y,head[x],z};
    head[x]=ne;
    return ;
}
void spfa(){
    memset(d,0x3f,sizeof(d));
    queue<int>q;
    q.push(1);
    d[1]=0;
    vis[1]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for (int i=head[u];i!=0;i=eg[i].next){
            int v=eg[i].to,w=eg[i].w;
            if (d[u]+w<d[v]){
                d[v]=d[u]+w;
                if (vis[v]==0){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return ;
}
int main(){
    freopen ("keepsake.in","r",stdin);
    freopen ("keepsake.out","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(a+n,b+n,c);add(a+2*n,b+2*n,c);
    }
    for (int i=1;i<=n;i++){
        int a;
        scanf("%d",&a);
        add(i,i+n,a);
        add(i+n,i+2*n,-a);
    }
    spfa();
    printf("%d\n",d[3*n]);
    return 0;
}