记录编号	565240	评测结果	AAAAAAAAAA
题目名称	旅游纪念	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.343 s
提交时间	2021-10-19 13:30:56	内存使用	7.92 MiB

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 200005;
int head[maxn],ver[maxn],nxt[maxn],cnt,dis[maxn];
int Head[maxn],Ver[maxn],Nxt[maxn],Cnt,Dis[maxn];
int dist[maxn],Dist[maxn],qwq[maxn],qaq[maxn];
void Add(int u,int v,int t) {
    Ver[++ Cnt] = v;
    Dis[Cnt] = t;
    Nxt[Cnt] = Head[u];
    Head[u] = Cnt;
    return ;
}
int n,m,price[maxn];
void add(int u,int v,int t) {
    ver[++ cnt] = v;
    dis[cnt] = t;
    nxt[cnt] = head[u];
    head[u] = cnt;
    return ;
}
queue<int> q;
bool vis[maxn];
void init(int* a,int val) {
	for(int i = 1;i <= n;++ i){
		a[i] = val;
	}
	return ;
}
void init(bool* a,bool val) {
	for(int i = 1;i <= n;++ i) {
		a[i] = val;
	}
	return ;
}
void SPFA_dis(int head[maxn],int ver[maxn << 1],int nxt[maxn << 1],int dist[maxn],int s) {
    while(!q.empty())q.pop();
    init(vis , false);
    init(dist , 0x3f3f3f3f);
    dist[s] = 0;
    q.push(s);
    vis[s] = true;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u];i;i = nxt[i]) {
            int v = ver[i],w = dis[i];
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if(!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return ;
}
void SPFA(int head[maxn],int ver[maxn << 1],int nxt[maxn << 1],int dist[maxn],int s,bool p) {
    while(!q.empty())q.pop();//infect BFS
    init(vis , false);
    if(p)init(qaq , 0x3f3f3f3f);//卖出 
    else init(qwq , 0x3f3f3f3f);//买入 
    if(p)qaq[s] = -price[s];
    else qwq[s] = price[s];
    q.push(s);
    vis[s] = true;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u];i;i = nxt[i]) {
            int v = ver[i];
            if(v == s)continue ;
            if(p) {
                int t = min(qaq[u] + dis[i] , dist[u] + dis[i] - price[v]);
                if(qaq[v] > t) {
                    qaq[v] = t;
                    if(!vis[v]) {
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }             
            else {
                int t = min(qwq[u] + dis[i] , dist[u] + dis[i] + price[v]);
                if(qwq[v] > t) {
                    qwq[v] = t;
                    if(!vis[v]) {
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
    }
    return ;
}
int main() {
    freopen("keepsake.in","r",stdin);
    freopen("keepsake.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;++ i) {
        int u,v,t;
        scanf("%d%d%d",&u,&v,&t);
        add(u , v , t);
        Add(v , u , t); 
    }
    for(int i = 1;i <= n;++ i)scanf("%d",&price[i]);
    SPFA_dis(head , ver , nxt , dist , 1);
    SPFA_dis(Head , Ver , Nxt , Dist , n);
    SPFA(head , ver , nxt , dist , 1 , false);
    SPFA(Head , Ver , Nxt , Dist , n , true);
    int ans = 0x3f3f3f3f;
    for(int i = 1;i <= n;++ i) {
        ans = min(ans , qaq[i] + qwq[i]);
    }
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}